考试的时候又想到了小凯的疑惑，真是中毒不浅...
设每一个数都可以被分成若干个$k$和$k+1$的和。数$x$能够被分成若干个$k$和$k+1$的和的充要条件是：
$x%k<=floor(x/k)$
又因为$k$一定小于这个数列中最小的那个数，可以轻易想到的一个朴素的方法就是从$1$到$A_{min}$枚举所有可能的$k$，判断是否满足情况，并更新答案。
注意到$k$越大，答案越优，所以从大到小进行枚举，找到答案就退出。
我们现在来优化他：
可以想到，当$k<=\sqrt{x}$，上述不等式一定成立。
所以只需要判断$k$在$(\sqrt{x},x]$范围内是否满足就可以了。
可是$x$在$1e9$的范围内，还是会超时呢。
其实我们枚举到了很多无用的$k$，因为要保证$A_{min}$也可以分成若干个$k$和$k+1$的和，所以实际上有效的$k$是：$A_{min}$,$A_{min}/2$,$A_{min}/3$...诸如此类的数...
我们可以枚举集合个数（$A_{min}$可以被拆成多少个数），然后通过集合个数来算$k$
枚举范围就从$(\sqrt{x},x]$变成了$(1,\sqrt{x}]$
在代码里，我特判了一下$1$的情况（其实是因为考试稳妥）
还有一些细节问题都放在注释里了
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<cmath>
using namespace std;
#define N 505
#define ll long long
int n;
int a[N];
ll ans;
int rd()
{
int f=,x=;char c=getchar();
while(c<''||c>''){if(c=='-')f=-; c=getchar();}
while(c>=''&&c<=''){x=(x<<)+(x<<)+(c^);c=getchar();}
return f*x;
}
int res=-;
bool check(int k,int ret,int id)
{//如果余数为0 有一次将k调整成k-1的机会
for(int i=;i<=n;i++)
{
int p=a[i]/k,q=a[i]%k;
if(ret&&q>p) return ;
if(!ret)
{
if(q>p)
{
k--;
ret=;
p=a[i]/k,q=a[i]%k;
}
if(q>p) return ;
}
}
res=k;
return ;
}
int main()
{
n=rd();
for(int i=;i<=n;i++)
a[i]=rd();
sort(a+,a+n+);
if(a[]==)
{
for(int i=;i<=n;i++)
{
if(a[i]&)
{
ans+=(a[i]-)>>;
ans++;
}
else ans+=(a[i]>>);
}
printf("%lld\n",ans+);
return ;
}
for(int i=;i<=int(sqrt(a[]))+;i++)
{//枚举集合个数 (对于最小的数)
int k=a[]/i;//集合大小 k和k+1
int ret=a[]%i;//如果是整除 就不能确定是k-1和k 还是k和k+1
//如果有余数 肯定是k和k+1(k还不够)
//如果余数为0 有一次将k调整成k-1的机会
if(check(k,ret,i))
break;
}
//printf("%d\n",res);
for(int i=;i<=n;i++)
ans+=(a[i]+res)/(res+);
printf("%lld\n",ans);
return ;
}
/*
2
948507270 461613425
*/
Code