題目鏈接：點(diǎn)擊查看

題目大意：給出一個(gè)長度為 n 的數(shù)列 a，現(xiàn)在可以對數(shù)列 a 進(jìn)行重新排序，規(guī)定：

如果 a[ i?] > m 的話，那么接下來 d 天的數(shù)字不做貢獻(xiàn)

否則沒有影響

問如何排列可以使得貢獻(xiàn)和最大

題目分析：想到了是貪心，但一開始的思路是對整個(gè)數(shù)列排序，然后每次用最大的大于 m 的值去抵消最小的 d 個(gè)數(shù)，如此往復(fù)，不過需要考慮好多細(xì)節(jié)，而且貪心策略也無法證明是最優(yōu)的，然后也沒實(shí)現(xiàn)出來

看了題解后才恍然大悟，其實(shí)可以將大于 m 的數(shù)和小于 m 的數(shù)分別儲存起來貪心排序儲存一下前綴和，然后去枚舉需要選擇多少個(gè)大于 m 的數(shù)即可，假設(shè)選了 x 個(gè)大于 m 個(gè)數(shù)，那么需要占用的位置：

最少是 ( x - 1 ) * ( d + 1 ) + 1，只需要將一個(gè)大于 m 的數(shù)放在末尾，剩下 x - 1 個(gè)數(shù)都占用 d + 1 個(gè)位置

最多是 x * ( d + 1 )，即每個(gè)數(shù)都占了 d + 1 個(gè)位置

那么剩余的空閑位置就是 n 減去占用的位置了，空閑位置的最大值顯然是對應(yīng)著上面的第一種情況，這些空閑位置都填上小于等于 m 的數(shù)即可

此時(shí)可能有人就有疑問了，假設(shè)剩下的空閑位置為 remain，remain 比小于等于 m 的數(shù)還要多怎么辦呢？分兩種情況討論一下即可：（設(shè) cnt 為小于等于 m 的數(shù)的個(gè)數(shù)）

remain - cnt <= d：此時(shí)還需要 remain - cnt 個(gè)大于 m 的數(shù)補(bǔ)充序列，因?yàn)槲覀兩厦娴那闆r 1 是將一個(gè)最大的數(shù)放在了末尾，只需要將這個(gè)數(shù)向前移動(dòng)，就可以使得這 remain - cnt 個(gè)大于 m 的數(shù)不做貢獻(xiàn)

remain - cnt > d：此時(shí)選擇的 x 一定不是最優(yōu)的，因?yàn)轱@然還可以再選擇一個(gè) x，所以繼續(xù)循環(huán)下去一定是可以到達(dá)最優(yōu)位置的

綜上所述，對于小于等于 m 的數(shù)，我們只需要選擇 min( cnt , remain ) 個(gè)即可

代碼：
?

//#pragma GCC optimize(2) //#pragma GCC optimize("Ofast","inline","-ffast-math") //#pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e6+100;LL sum1[N],sum2[N];int a[N],b[N],c1,c2;int main() { #ifndef ONLINE_JUDGE // freopen("data.ans.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int n,d,m;scanf("%d%d%d",&n,&d,&m);for(int i=1;i<=n;i++){int num;scanf("%d",&num);if(num>m)a[++c1]=num;elseb[++c2]=num;}sort(a+1,a+1+c1,greater<int>());sort(b+1,b+1+c2,greater<int>());for(int i=1;i<=c1;i++)sum1[i]=sum1[i-1]+a[i];for(int i=1;i<=c2;i++)sum2[i]=sum2[i-1]+b[i];LL ans=sum2[c2];for(int i=1;i<=c1;i++){int day=(i-1)*(d+1)+1;if(day>n)break;ans=max(ans,sum1[i]+sum2[min(n-day,c2)]);}printf("%lld\n",ans);return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的CodeForces - 1395D Boboniu Chats with Du(贪心)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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