P14544 报告 题解

· · 题解

1. 题意解释

最大化 \sum\limits_{i=1}^n(a_i\bmod t) 的值。

2. 思路

取模不好做所以我们考虑转化。

把式子拆开变成 \sum\limits_{i=1}^n(a_i-t\lfloor\dfrac{a_i}{t}\rfloor)=\sum\limits_{i=1}^na_i-\sum\limits_{i=1}^nt\lfloor\dfrac{a_i}{t}\rfloor。

前式为定值，考虑怎么干后面的式子。

不难发现如果 a_i 是单调的话后面的 \lfloor\dfrac{a_i}{t}\rfloor 也单调，可以优化掉一重循环。

具体做法是在枚举 t 的内层循环中枚举 t 的所有倍数 k，如果现在处理到的 a_i 满足 k\le a_i 且 a_i<k+t，则 t\lfloor\dfrac{a_i}{t}\rfloor=a_i-k，然后让 i 加一。

于是做完了，复杂度为 O(n\log n)，如果使用桶排可以做到 O(\max\limits_{i=1}^na_i)。

3. 代码实现

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a[200200],maxn=-1e9,minn=1e9,ans,sum;
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        maxn=max(a[i],maxn);
        minn=min(a[i],minn);
        sum+=a[i];
    }
    sort(a+1,a+1+n);
    for(int t=1;t<=minn;t++){
        int now=1,cnt=0;
        for(int j=1;t*j<=maxn;j++){
            while(t*j<=a[now]&&a[now]<t*(j+1)){
                cnt+=j;
                now++;
            }
        }
        ans=max(ans,sum-t*cnt);
    }
    cout<<ans;
    return 0;
}