解析

把題目標(biāo)簽寫在數(shù)據(jù)范圍上的一道題
由于k過大，顯然無法dp
那就只能貪了

一開始被完全帶跑偏了…
想的是把序列降序排列然后從后往前劃分…
這個(gè)思路能很簡(jiǎn)單的寫出nkdp
然后就卡住了…
算看了一半題解吧
看到第一段“考慮分成k組”后退出來了
有了這個(gè)線頭后面就非常順
以后還是要努力培養(yǎng)在推不出好的性質(zhì)時(shí)打破第一印象的能力

考慮正解
清零k次等價(jià)于把boss分成不多于k組
每次把新元素加入的同時(shí)獲得原來集合內(nèi)元素和的代價(jià)
所以只需要維護(hù)集合的元素和即可

考慮把所有集合放入大根堆
降序加入元素
顯然正的元素直接全放一組是最好的

如果現(xiàn)在是負(fù)的元素
如果堆頂還是正的那就加進(jìn)去，不難發(fā)現(xiàn)，因?yàn)楹竺娴脑馗?#xff0c;這樣能盡可能讓這個(gè)集合發(fā)揮余熱（性感理解一下），肯定還是好的
如果堆頂負(fù)了我們就盡可能的讓新元素成為一個(gè)新的集合
感性理解一下，在啥都是負(fù)的時(shí)候，我們肯定是讓所有的元素從大到小蛇形分布，這樣使產(chǎn)生貢獻(xiàn)的元素都是相對(duì)負(fù)的不厲害的
如果極小值全塞到一起肯定是不好的
（為什么我的貪心分析全是感性理解啊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); } /* 1 281239 */

總結(jié)

以上是生活随笔為你收集整理的CF1415E New Game Plus（贪心）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。