P6346 题解

Epi4any · 2023-07-26 12:12:50 · 题解

总是能看到一些神奇的做法，我也不知道怎么想出来的，此处献上一个并查集解法。（个人认为很好理解，而且不是那种莫名其妙的做法）

1. 把 b_i 由大到小排序，因为我们想要白嫖价值最高的数。
2. 把 b_i 安排到一个序列 p 里，这个序列表示交的第 i 个朋友为 p_i。

然后我们分析如何搞好 p，让其开销最小，此时我们不难想到应该先安排价值最大的那个点。简而言之，我们把 b_i 放到 p 中从 a_i+1 到 n 中第一个没有被用过的地方，如果没有这个位置，我们就把那个人买下来，然后放到 1 到 n 的第一个空位上。

对于查找 p_k 到 p_n 第一个空位的下标，我们用并查集维护，注意要路径压缩。

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
struct Node {
    int a,b;
    bool operator<(const Node x) const {
        return b>x.b;
    }
} in[maxn];
int n,fa[maxn],size[maxn],p[maxn],ans;
void init() {
    for(int i=1;i<=n+1;i++){
        fa[i]=i,size[i]=1;
    }
}
int getf(int x){
    if(fa[x]==x) return x;
    else {
        fa[x]=fa[fa[x]];
        return getf(fa[x]);
    }
}
inline void merge(int x,int y){
    int fx=getf(x),fy=getf(y);
    if(fx==fy) return;
    fa[fx]=fy,size[fy]+=size[fx];
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++) {
        cin>>in[i].a>>in[i].b;
    }
    sort(in+1,in+n+1);/*
    for(int i=1;i<=n;i++) {
        cout<<in[i].a<<" "<<in[i].b<<endl;
    }*/
    init();
    for(int i=1;i<=n;i++) {
        int fx=getf(in[i].a+1);
        if(fx<n+1) {
            merge(fx,fx+1);
            p[fx]=in[i].b;
        } else {
            int pos=getf(1);
            merge(pos,pos+1);
            ans+=in[i].b;
        }
    }
    cout<<ans<<endl;
    return 0;
}