我可能是 \(zz\) 吧,估错复杂度,发呆了半天 …..

推下式子变成求 \((1-x)\sum \lfloor \frac{a_i}{x} \rfloor\) 的最小值。然后直接暴力枚举 \(x\) ,每次 \(O(\frac{\max a_i}{x})\)

调和级数,所以 \(O(n \log n)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=1000005;
int n,m,sum[maxn];
LL ans,_min;
int main(){
freopen("uoj21.in","r",stdin);
freopen("uoj21.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++){
int x; scanf("%d",&x);
ans+=x; sum[x]++;
}
for(int i=1;i<=1000000;i++) sum[i]+=sum[i-1];
for(int x=2;x<=1000000;x++){
LL res=0;
for(int j=1;j*x<=1000000;j++) res+=(LL)(sum[min(1000000,x*(j+1)-1)]-sum[x*j-1])*j;
_min=min(_min,res*(1-x));
}
printf("%lld\n",ans+_min);
return 0;
}