解析
把题目标签写在数据范围上的一道题
由于k过大，显然无法dp
那就只能贪了
一开始被完全带跑偏了…
想的是把序列降序排列然后从后往前划分…
这个思路能很简单的写出nkdp
然后就卡住了…
算看了一半题解吧
看到第一段“考虑分成k组”后退出来了
有了这个线头后面就非常顺
以后还是要努力培养在推不出好的性质时打破第一印象的能力
考虑正解
清零k次等价于把boss分成不多于k组
每次把新元素加入的同时获得原来集合内元素和的代价
所以只需要维护集合的元素和即可
考虑把所有集合放入大根堆
降序加入元素
显然正的元素直接全放一组是最好的
如果现在是负的元素
如果堆顶还是正的那就加进去，不难发现，因为后面的元素更小，这样能尽可能让这个集合发挥余热（性感理解一下），肯定还是好的
如果堆顶负了我们就尽可能的让新元素成为一个新的集合
感性理解一下，在啥都是负的时候，我们肯定是让所有的元素从大到小蛇形分布，这样使产生贡献的元素都是相对负的不厉害的
如果极小值全塞到一起肯定是不好的
（为什么我的贪心分析全是感性理解啊qwq）
代码
#include<bits/stdc++.h>
const int N=1e6+100;
const int mod=1e9+7;
#define ll long long
using namespace std;
inline ll read() {
ll x(0),f(1);char c=getchar();
while(!isdigit(c)) {if(c=='-')f=-1;c=getchar();}
while(isdigit(c)) {x=(x<<1)+(x<<3)+c-'0';c=getchar();}
return x*f;
}
int n,m;
ll a[N],ans;
bool cmp(ll x,ll y){
return x>y;
}
priority_queue<ll>q;
int main(){
n=read();m=read();++m;
for(int i=1;i<=n;i++) a[i]=read();
sort(a+1,a+1+n,cmp);
for(int i=1;i<=n;i++){
ll x=a[i];
if(q.empty()||(q.top()<0&&(signed)q.size()<m)){
q.push(x);
}
else{
ll o=q.top();q.pop();
ans+=o;o+=x;
q.push(o);
}
}
printf("%lld\n",ans);
}
|