题目描述
林先森买了n棵树苗，种在一条直线上，用来装点他的花园。初始时所有树苗的高度是0,每过1天每棵树苗都会长高一米。对每棵树苗，林先森希望它的最终高度为$a_i$，因此他会定时检查树苗的情况，并及时砍掉过高的树苗。具体来说，从种下所有树苗开始，每d天（即：第d天、第2d天，...，以此类推）林先森会检查一边所有的树苗，如果有树苗的高度不低于他希望的高度，林先森会把高出的部分（可以为0）砍掉，之后这棵树苗便不再长高。由于砍树是一件辛苦的工作，林先森希望砍掉的树苗的总长度不超过k米。在这个前提下，为了偷懒，林先森想要知道最大可能的d值。
输入格式
第一行两个整数n，k，代表树苗的数量和最大看书的总长度。
第二行n个整数$a_i$，代表林先森希望每棵树苗的最终高度。
输出格式
一行一个整数，代表最大可能的d值。
样例
样例输入：
3 4
1 3 5
样例输出：
3
数据范围与提示
样例解释：
第3天林先森砍掉了第一和第二棵树苗，第6天林先森砍掉了第三棵树苗。总共砍树的长度为$(3-1)+(3-3)+(6-5)=3$米。可以证明更大的d值无法满足要求。
数据范围：
对于20%的数据，$a_i ≤ {5×10}^5$。
另有20%的数据，$k≤1$。
对于所有的数据，$1≤n≤100$，$0≤k≤{10}^{11}$，$1≤a_i≤{10}^9$。
题解
看到k很大，n很小，优先选择从n入手。
20%算法：
暗中观察数据范围，有20%的数据$k≤1$，怎么办呢？
这个时候分为两种情况：
1.k=0，那么就是说我们每一次都要赶巧了在这棵树苗长到最终高度那一天砍掉，所以答案即为所有最终高度的最大公约数。
2.k=1，因为n比较小，所以我们每次枚举树苗，将它的最终高度+1，然后再求所有树苗的最终高度的最大公约数，取最大值即可。
期望得分：20分。
40%算法：
开始推式子，设这个天数为d，那么砍掉树苗i的高度即为$\left \lceil \frac{a_i}{d} \right \rceil \times d$，那么，可以列出式子：
$\sum \limits_{i=1}^{n} \left \lceil \frac{a_i}{d} \right \rceil \times d - a_i \leqslant k$
移项得：$\sum \limits_{i=1}^{n} \left \lceil \frac{a_i}{d} \right \rceil \times d \leqslant k + \sum \limits_{i=1}^{n} a_i$
惊喜发现上面不等式右边是定值，于是我们设$k + \sum \limits_{i=1}^{n} a_i$为$C$，先让d=1，每次让d++，当$d \geqslant \min a_i + k$时，不可能在有答案，所以这就是d的上界。
期望多得分数：10分。
100%算法：
显然，40%时间复杂度还是不允许，但是我们发现，有的d没有必要枚举。
注意对于每个$a_i$，$\left \lceil \frac{a_i}{d} \right \rceil$只有$\sqrt{a_i}$种不同的取值，因此，$\sum \limits_{i=1}^{n}\left \lceil \frac{a_i}{d} \right \rceil$只有$n \times \sqrt{a_i}$种不同的取值，利用数论分块，可以知道下一个d为$\frac{C}{\left \lceil \frac{C}{d+1} \right \rceil}$。
时间复杂度：$O( \sqrt{(\min a_i + k) \times n})$。
期望得分：100分。
代码时刻
20%算法：
#include<bits/stdc++.h>
using namespace std;
int n,k;
long long a[1000001];
long long ans;
long long gcd(long long x,long long y)
{return y==0?x:gcd(y,x%y);}
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
scanf("%lld",&a[i]);
if(!k)//特判k==0
{
ans=a[1];
for(int i=2;i<=n;i++)
ans=gcd(ans,a[i]);
printf("%lld",ans);
}
if(k==1)//特判k==1
{
long long flag=a[2];
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(i!=j)flag=gcd(flag,a[j]);
else flag=gcd(flag,a[j]+1);//将它+1
}
ans=max(ans,flag);
flag=a[1];
}
printf("%lld",ans);
}
return 0;
}
40%算法（记得加上上面代码的那一段）：
#include<bits/stdc++.h>
using namespace std;
int n;
long long a[100001];
long long sigma;
long long ans;
int main()
{
scanf("%d%lld",&n,&sigma);
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
sigma+=a[i];
}
for(long long d=1;d<=sigma;d++)
{
long long flag=0;
for(int i=1;i<=n;i++)
{
if(a[i]%d)flag+=(a[i]/d+1)*d;
else flag+=a[i];
}
if(flag<=sigma)ans=d;
}
printf("%lld",ans);
return 0;
}
100%算法：
#include<bits/stdc++.h>
using namespace std;
int n;
long long k;
long long a[1000001];
long long sigma,maxn;
long long ans;
int main()
{
scanf("%d%lld",&n,&k);
sigma=k;
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
sigma+=a[i];
maxn=max(maxn,a[i]);
}
maxn+=k;
long long d=1;
while(1)
{
long long flag=0;
for(int i=1;i<=n;i++)
{
if(a[i]%d)flag+=(a[i]/d+1)*d;
else flag+=a[i];
}
if(flag<=sigma)ans=d;
if(maxn<=d)break;//上界
d=sigma/(sigma/(d+1));//更新d
}
cout<<ans<<endl;
return 0;
}
rp++