解析
把题目标签写在数据范围上的一道题
由于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 longusing 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);}/*1281239*/