题目:

小O是一个热爱短代码的选手。在缩代码方面，他是一位身经百战的老手。世界各地的OJ上，很多题的最短解答排行榜都有他的身影。这令他感到十分愉悦。

最近，他突然发现，很多时候自己的程序明明看起来比别人的更短，实际代码量却更长。这令他感到很费解。经过一番研究，原来是因为他每一行的缩进都全是由空格组成的，大量的空格让代码量随之增大。

现在设小O有一份 \(n\) 行的代码，第 \(i\) 行有 \(a_i\) 个空格作为缩进。

为解决这一问题，小O要给自己文本编辑器设定一个正整数的默认TAB宽度 \(x\)，然后对于每一行，编辑器从头至尾不断把连续 \(x\) 个空格替换成一个TAB，直到剩余空格数不足 \(x\) 个。

最终缩进所占代码量为空格数与TAB数的和。请你帮小O选择一个合适的 \(x\)，使得缩进所占代码量最小。

题解:

我们容易发现对于一个确定的\(x\),答案即为\(\sum_{i=1}^n[\frac{a_i}{x} + (a_i \mod x)]\)

因为有一个模运算,所以我们不好求值.

我们考虑去掉这个模运算.我们考虑计算每个转化可以减少多少代码量.

对于一个\(siz\)为\(x\)的的TAB转化,可以减少\(x-1\)的代码量.

所以我们发现对于一个确定的x,可以减少的代码量为\((x-1)\sum_{i=1}^n[\frac{a_i}{x}]\)

然后我们考虑枚举,

首先我们枚举\(x\),然后枚举\([\frac{a_i}{x}]\)的值

然后可以利用桶统计在\([x*\frac{a_i}{x},x*(\frac{a_i}{x}+1))\)内的数的个数

更新答案即可.

容易发现这是\(O(nlogn)\)的.

#include 
    
     #include 
     
      #include 
      
       using namespace std;typedef long long ll;#define rg register intinline void read(int &x){    x=0;char ch;bool flag = false;    while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;    while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;}const int maxn = 1000010;int c[maxn];int main(){    int n;read(n);    int m = 0;ll ans = 0;    for(rg i=1,x;i<=n;++i){    read(x);m = max(m,x);    ++ c[x];ans += x;    }    for(rg i=1;i<=m;++i) c[i] += c[i-1];    ll del = 0,res = 0;    for(rg x = 2;x <= m;++x){    res = 0;    for(rg y=1;y <= (m/x);++y){        res += 1LL*y*(c[min(x*(y+1)-1,m)] - c[x*y-1]);    }    del = max(del,res*(x-1));    }    printf("%lld\n",ans-del);    return 0;}