自动搬运

查看原文

来自洛谷，原作者为

	Epi4any No more slacking off, last chance to win

搬运于2025-08-24 22:19:54，当前版本为作者最后更新于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;
}