CF1415E New Game Plus! 题解

解题思路

简单贪心题，我们可以把整个序列看作 \(k+1\) 个可重集，首先可以得到一个显然的结论：较大的数一定比较小的数先放入一个集合中。同样，由于每一轮 \(ans\gets ans+\max sum_i\)，其中 \(sum_i\) 表示第 \(i\) 个集合的元素和，那么，我们一定会将当前的元素放入当前和最大的哪个集合。

综上，本题步骤如下：

• 初始将每个集合的值赋为 \(0\)；
• 将数组从大到小排序，先把大的加入集合；
• 将 \(ans\gets ans+\max sum_i\)；
• 取出最大的哪个集合，然后将当前元素加入并重新计算最大的集合。

AC 代码

#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include <set>
#include <map>
#define ll long long
#define int ll
#define N 500005
int n,k,c[N];ll sum,ans;
inline bool cmp(int a,int b){
    return a>b;
}
struct Cmp{
    inline bool operator ()(
        const int a,
        const int b
    ) const {
        return a>b;
    }
};
std::set<ll,Cmp> s;
std::map<ll,ll> m;
signed main(){
    scanf("%lld%lld",&n,&k);int l;
    for(register int i=1;i<=n;++i)
        scanf("%lld",&c[i]);
    std::sort(c+1,c+n+1,cmp);
    for(register int i=1;i<=k+1;++i)
        ++m[0];s.insert(0);
    for(register int i=1;i<=n;++i){
        auto now=*s.begin();
        --m[now];if(!m[now])
            s.erase(now);
        ans+=now;++m[now+c[i]];
        s.insert(now+c[i]);
    }printf("%lld",ans);
}