2022牛客寒假算法基础集训营2，小沙的魔法（并查集，离散化）

传送门

思路：

区间从0增加到目标值，等价于初始就是区间目标值情况下，每次使得区间-1，最后使目标值全部变成0，那么整体思路就是先把高的点降下去，然后等到这个边连接的两个点高度相同的时候，把他们连接起来，所以我们可以找到每边的两个点高度较低的那个作为这个边的权值（高度降到较低的那个时，才是两点相连的时候），将边权从大到小排序，从大到小遍历，在遍历过程中寻找所在连通块，进行合并（抽象成一个点，让他们高度相同），由于权值过大，所以离散化一下即可

代码：

#include <bits/stdc++.h>
using namespace std;

const int maxn=5000000+50;
int n,m,T,a[maxn],sum[maxn],f[maxn];

struct node{
    int l,r,w;
}l[maxn];
long long ans;

bool cmp(node x,node y){
    return x.w>y.w;
}

int find(int x){
    if (f[x]==x) return x;
    return f[x]=find(f[x]);
}

int main(){
    scanf("%d%d",&n,&m);
    for (int i=1; i<=n; ++i)
        scanf("%d",&a[i]),f[i]=i;
        
    for (int i=1; i<=m; ++i){
        scanf("%d%d",&l[i].l,&l[i].r);
        l[i].w=min(a[l[i].l],a[l[i].r]);
    }
    sort(l+1,l+m+1,cmp);
    
    for (int i=1; i<=m; ++i){
        int f1=find(l[i].l),f2=find(l[i].r);
        if (f1==f2) continue;
        
        //各个连通块中非最小值与最小值的差分
        //差就是那个点需要减低到什么时候这条边才能相连
        ans+=max(a[f1],a[f2])-min(a[f1],a[f2]);
        a[f1]=a[f2]=min(a[f1],a[f2]);
        f[f1]=f2;
    }
    for (int i=1; i<=n; ++i)
    	//各个连通块中的最小值
        if (find(i)==i) ans+=a[i];
    printf("%lld\n",ans);
    return 0;
}