P7891 [入门赛 #10] Coin Selection G（hard version） 题解

· · 题解

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

感谢 @zhuweiqi 指出重大错误。

题目大意：

给定 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;
}