自动搬运

查看原文

来自洛谷，原作者为

	GeorgeAAAADHD will AFO

搬运于2025-08-24 22:34:00，当前版本为作者最后更新于2023-03-23 12:41:43，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

注：本题作者使用二分算法。

感谢

题目大意：

给定 $n$ 和 $n$ 个正整数 $a_i$，你需要输出两个数字 $sum1$ 和 $sum2$。

总共执行 $n$ 次操作，当这次操作为第奇数次操作时，在所有 $a_i$ 中找到一个最大但不超过 $sum1$ 的 $a_i$，加上它并将它删去。如果所有 $a_i$ 均大于 $sum1$，将 $sum1$ 加上最小的 $a_i$ 并将这个 $a_i$ 删去。如果这次操作是第偶数次操作，则对 $sum2$ 执行同样的操作。

数据范围：$1 \le n \le 10^5$，$1 \le a_i \le 10^9$。

分析：

暴力枚举是 $O(n^2)$ 算法，肯定超时。

于是我们思考一下二分的做法。

发现将 $a_i$ 升序排序后，可以利用二分查找最大但不超过 $sum1$ 或 $sum2$ 的 $a_i$。注意排序时应写成 sort(a.begin(),a.end());。

然后我们用一个 vector 存储所有 $a_i$，动态维护这个 vector，每次操作后将要删除的 $a_i$ 删除就可以了。这个地方需要用到 iterator，即迭代器，可以自行上网搜索。

于是我们便愉快地 AC 了本题。

注：$sum1$ 和 $sum2$ 的最终结果有可能会超过 int 范围，因此我们要开 long long。

Code:

#include<bits/stdc++.h>
using namespace std;
long long n,suma=0,sumb=0,k;
bool f=1;
vector<long long> a;
void add(long long &sum){
	int l=0,r=a.size()-1,ans=0,x=0;
	while(l<=r){
		int mid=(l+r)/2;
		if(a[mid]<=sum){
			x=mid;
			ans=a[mid];
			l=mid+1;
		}
		else r=mid-1;
	}
	if(!ans){
		sum+=a[0];
		a.erase(a.begin());
	}
	else{
		sum+=a[x];
		a.erase(a.begin()+x);
	}
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>k;
		a.push_back(k);
	}
	sort(a.begin(),a.end());
	for(int i=1;i<=n;i++){
		if(f)add(suma);
		else add(sumb);
		f=!f;
	}
	cout<<suma<<' '<<sumb;
}