[pixiv] https://www.pixiv.net/member_illust.php?mode=medium&illust_id=60638239
description
有n棵竹子，初始时每棵竹子高度都是0，每棵竹子每天长高1m
对于每棵竹子，我们不希望其高度超过a[i]，如果超过了，我们就会把超过的部分减去
奇怪的是减去之后竹子就不会再长了
我们不希望每天去看一下竹子的情况，希望每隔d天去看一下竹子的情况
本着爱护环境的原则，我们不希望减去的竹子长度之和大于K
我们最多可以隔多少天去看一次竹子？
input
第一行两个整数n，K
第二行n隔整数表示a[i]
output
一个整数表示答案，即最大的d值
hint
20%:ai<=5*10^5
另有20%:k<=1
100%:1<=n<=100,0<=k<=10^11,1<=ai<=10^9
这道题我还愣是问大佬问了好久才搞懂。
第一眼：而不是二分嘛，水！结果考试快结束是才反应过来这答案并不满足二分的性质。如：4 4 4，d选4比选3优。
那么怎么办呢？
首先可以明确，d一定小于a[i]的最大值。那么这个d就太多了啊。如果直接暴力去for d，肯定是不行的，只能得20分。我们希望可以减少一些无用的d的枚举。
先可以得到公式：
转化一下：
我们可以发现，对于[ai/d]向上取整，有多个d对应相同的值。如：10/d，d=5,6,7,8,9都对应一个值2，可以证明d的数量是o（√n）
我们记录每一个ai对应的d，其中d可以代表一系列d。在算出了sigma（[ai/d]）后，可以根据上面的公式求出最大的d
暴力枚举得出的d，复杂度o(n*ai^0.5)
详情看代码吧。。。解释起来好麻烦。。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int N=105;
const int M=100000+5;
ll a[N],n,k,c=0;
ll ans=0,tot=0,vec[N*M],cnt=0;
int main(){
scanf("%lld%lld",&n,&k);
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
c+=a[i];
for(int j=1;j*j<=a[i];j++)
vec[++cnt]=j,vec[++cnt]=(a[i]-1)/j+1;
}
c+=k;
sort(vec+1,vec+cnt+1);
cnt=unique(vec+1,vec+cnt+1)-(vec+1);
for(int i=1;i<=cnt;i++){
ll d=vec[i];
tot=0;
for(int j=1;j<=n;j++)
tot+=(a[j]-1)/d+1;
if(c/tot<d) continue;
ans=max(ans,c/tot);
}
printf("%lld",ans);
return 0;
}总结：
1、在想二分时可以举例子来验证答案的单调性
2、把公式写出来时，可以结合一些数论的知识，看看能不能化简