题解 CF1415E 【New Game Plus!】

gyh20 · 2020-12-12 22:30:25 · 题解

首先，看到数据范围里 n,k 都是 5\times 10^5，可以猜想是 O(n\log n) 算法，这个东西感觉不是很好 DP，于是我想到了贪心。

由于带 \log，首先考虑堆贪心。

由于我们可以进行 k 次操作，我们可以看成分为 k+1 组，每一组内部自选。

首先，每一组内部一定是不上升的，否则交换两个位置一定更优。

所以我们先要把 a 排序。

then？

令第 i 组当前的元素总和为 sum_i 那么当我们将一个价值 x 的值加入时，ans+=sum_i,sum_i+=x。

可以发现，当选择最大的 sum_i 时一定不劣（收益一定）。

用一个堆维护即可。

代码实现非常简单，没有任何细节。

#include<bits/stdc++.h>
#define re register
#define int long long
using namespace std;
inline int read(){
    re int t=0,f=0;re char v=getchar();
    while(v<'0')f|=(v=='-'),v=getchar();
    while(v>='0')t=(t<<3)+(t<<1)+v-48,v=getchar();
    return f?-t:t;
}
priority_queue<int>q;
int n,m,t,a[1000002],h[1000002];
long long ans,sum;
signed main(){
    n=read(),m=read();
    for(re int i=1;i<=n;++i)a[i]=read();
    sort(a+1,a+n+1),reverse(a+1,a+n+1);
    for(re int i=1;i<=m+1;++i)q.push(0);
    for(re int i=1;i<=n;++i){
        int xx=q.top();
        q.pop();
        ans+=xx;
        xx+=a[i];
        q.push(xx);
    }
    printf("%lld",ans);
}