<span>Codeforces Round #664 (Div. 2) D. Boboniu Chats with Du</span>
传送门：cf1395D
题意
给定一个长度为n的数组a[i]为当天说话的有趣值，如果a[i]>m，那么在 i 之后有d天不能说话。否则可以每天都说话。找到一个排列使得n天有趣值总和最大，问有趣值总和的最大值是多少。
题解
很明显用贪心。先取>m的有趣值直到取不下。根据样例1的解释可以看出将一个大于m的值放在最后，前边放<m的会更优，所以此时有两种情况，如果取了的p个大于m的值p*(d+1)（p个大于m的总共占了多少天）大于n，那么就要找到最后一个能说话的天后不能说话的天数，即d-(p*(d+1)-n)，然后可以加上<m最大的前d-(p*(d+1)-n)天，相当于把这段放在最后说话的那天前边。如果p*(d+1)<=n，剩下的位置就可以直接由大到小放<m的有趣值，因为最后一个>m的值后边也有d天不能说话，所以也将最后一个>m的值移到最后，相当于再加上d个<m的值，和前边的做法一样。然后就可以开始用<m的段替换>m的段，如果长度为d+1的<m的剩余的值和的最大值比所取的>m的值的最小值大，那么就可以直接用这一段替代>m的那一段，直到没有这样的段可以替代位置。
说的绕绕的，当时想的就绕绕的，代码还行，好像是有更简便的做法的。
代码
1 #include<bits/stdc++.h> 2 #define ll long long 3 using namespace std; 4 5 ll a[100100]; 6 ll b[100100]; 7 8 ll cmp(ll x,ll y) 9 { 10 return x>y; 11 } 12 13 int main() 14 { 15 ios::sync_with_stdio(false); 16 cin.tie(0); 17 cout.tie(0); 18 ll n,m,d; 19 cin>>n>>d>>m; 20 for(ll i=0;i<n;i++) cin>>a[i]; 21 sort(a,a+n,cmp); 22 ll ans=0; 23 ll k=0,p=0,q=0; 24 for(ll i=0;i<n;i++){ 25 if(a[i]<=m) b[k++]=a[i]; 26 } 27 ll cnt=0; 28 for(ll i=0;i<n-k;i++){ 29 if(cnt>=n) break; 30 cnt++; 31 ans+=a[i]; 32 cnt+=d; 33 p++; 34 } 35 p--; 36 for(ll i=cnt;i<n;i++) ans+=b[q++]; 37 if(k==0) {cout<<ans<<endl;return 0;} 38 if(cnt>n){ 39 ll res=0; 40 ll pp=cnt-n; 41 pp=d-pp; 42 for(ll i=q;i<min(q+pp,k);i++) res+=b[i]; 43 q+=pp; 44 ans+=res; 45 } 46 else{ 47 ll res=0; 48 for(ll i=q;i<min(q+d,k);i++) res+=b[i]; 49 q+=d; 50 ans+=res; 51 } 52 while(q<k&&p>=0){ 53 ll res=0; 54 for(ll i=q;i<min(q+d+1,k);i++) res+=b[i]; 55 if(res>a[p]) ans-=a[p],ans+=res,p--; 56 else break; 57 q+=d+1; 58 } 59 cout<<ans<<endl; 60 return 0; 61 }
投递中国石油等公司10个岗位 >