以下令 $amax =\max_{i=1}^n{a_i}$。
分类讨论：
如果能用 $K$ 次将其全部补到 $amax$，那当然最好。
如果 $K$ 还没有用完，那就接着补齐，可以证明此时的 $\gcd$ 一定最大。
否则，这个数列的 $\gcd$ 一定不会超过 $amax$，枚举这个 $\gcd$ 从 $amax$ 到 $1$，很简单做出 $O(amax \times n)$ 的做法。
然而 TLE 了。怎么办呢？设现在枚举到 $x$，注意到 $a$ 中的数一定在区间 $(0,x],(x,2x],(2x,3x]…(kx,n]$ 中的一个，前缀和优化就可以做到 $O(\frac{n}{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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
|
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,total;
int k;
int a[300005];
int t[300005],pret[300005];
signed main(){
scanf("%lld%lld",&n,&k);
int maxval=0;
for(int i=1;i<=n;i++){
scanf("%lld",a+i);
++t[a[i]];
total+=a[i];
maxval=max(maxval,a[i]);
}
int diff=0;
for(int i=1;i<=n;i++){
diff+=maxval-a[i];
}
if(k>=diff){
printf("%lld",maxval+(k-diff)/n);
exit(0);
}
for(int i=1;i<=maxval;i++){
pret[i]=t[i]+pret[i-1];
}
for(int i=maxval;i>1;i--){
int ans=0;
int x;
for(x=i;x-i<maxval;x+=i){
if(x<=maxval)ans+=(pret[x]-pret[x-i])*x;
else ans+=(n-pret[x-i])*x;
}
ans-=total;
if(ans<=k)printf("%lld",i),exit(0);
}
puts("1");
return 0;
}
|