题目链接

解题思路

我们将 $>m$ 和 $<=m$ 的数字归为两组a,b，两组可独立考虑。对于每一组中，都取最大的几个。
如果我们取了 $i$ 个b，则b只能取 $(n-i-1)/(d+1)+1$ 个。穷举i即可在 $O(nlogn)$ 的时间内得到答案。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,d,m;
int a[100005];
int cnt=0;
int ans=0;
int suma[100005],sumb[100005];
int aa[100005],bb[100005];
bool cmp(int aa,int bb){
    return aa>bb;
}
int cnta,cntb;
signed main(){
    cin>>n>>d>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(a[i]>m)aa[++cnta]=a[i];
        else bb[++cntb]=a[i];
    }
    sort(aa+1,aa+cnta+1,cmp);
    sort(bb+1,bb+cntb+1,cmp);
    int tot=0;
    for(int i=1;i<=cnta;i++)suma[i]=suma[i-1]+aa[i];
    for(int i=1;i<=cntb;i++)sumb[i]=sumb[i-1]+bb[i];
    for(int i=0;i<=n;i++){
        tot=sumb[i]+suma[(n-i-1)/(d+1)+1];
        ans=max(ans,tot);
    }
    cout<<ans<<endl;
    return 0;
}

PS：每次cf都想不到枚举（哭

本文链接：http://kaispace.com.cn/index.php/archives/687/

如果未注明出处，复制公开后需将注明本博客链接。
打赏作者