CF1394A Boboniu Chats with Du

考虑贪心设数组b和c分别表示a[i]m的不会被禁言的数组以及m的会被禁言的数组。将b和c从大到小排序设sumb[i]为从1~i的b数组的前缀和。初始的答案就是sumb[cntb]这是下限了然后枚举c数组用res变量表示取前i个c数组的值的和那选i个c数组要被禁言多少时间呢每次来一次c就会花(d1)的时间(禁言d天嘲讽1天)然后这样的情况会有(i-1)天因为最后一天禁言是不用管的只有嘲讽用的一天。时间int day(i-1)*(d1)1;那么不用禁言的b数组能选多少呢lmin(n-day,cntb); (n-day)是剩余的天数但如果你只有cntb天也只能剩下一些天不用了。代码(求赞)#includebits/stdc.h using namespace std; #define int long long const int N1e55; int n,d,m,cntb0,cntc0,a[N],b[N],c[N],sumb[N];//b数组为a[i]m值c数组为a[i]m的值。 bool cmp(int x,int y){ return xy; } signed main(){ scanf(%lld%lld%lld,n,d,m); for(int i1;in;i){ scanf(%lld,a[i]); if(a[i]m){ b[cntb]a[i]; }else{ c[cntc]a[i]; } } sort(b1,bcntb1,cmp); sort(c1,ccntc1,cmp); for(int i1;icntb;i){ sumb[i]sumb[i-1]b[i]; } int anssumb[cntb],res0; for(int i1;icntc;i){ resc[i]; int day(i-1)*(d1)1; if(dayn) break; int lmin(n-day,cntb); ansmax(ans,sumb[l]res); } printf(%lld,ans); return ~(-1); }