数学 砍树

Σ (向上取整（a[i]/d）*d-a[i])<=k
Σ（向上取整(a[i]/d)）<=k+Σa[i]（总称为C）
Σ向上取整（a[i]/d）<=向下取整（C/d）；
f(d)=Σ向上取整（a[i]/d）,g(d)=向下取整（C/d）
易知两个函数都是单调不上升的。具体来说都是分段的，那么对于g(d)的同一段上，段尾的d值一定优于段首值（f(d)也单调下降）。
那么枚举每一个段尾的d值，暴力求f(d),更新答案即可。
PS：设段首为i,段尾=C/(C/i);神奇。。

#include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> #include<cmath> #define ll long long using namespace std; int n; ll k,a[105],ans; inline int read() {int sum=0,f=1;char x=getchar();while(x<'0'||x>'9'){if(x=='-')f=-1;x=getchar();}while(x>='0'&&x<='9'){sum=(sum<<1)+(sum<<3)+x-'0';x=getchar();}return sum*f; } int main() {n=read();scanf("%lld",&k);for(int i=1;i<=n;i++)scanf("%lld",&a[i]),k+=a[i];ll i=1,j,t;while(1){t=k/i;if(t==0)break;j=k/t;ll sum=0;for(int l=1;l<=n;l++){ll h=a[l]/j;if(h*j<a[l])h++;sum+=h;if(sum>t)break;}if(sum<=t)ans=j;i=j+1;} cout<<ans; }

转载于:https://www.cnblogs.com/QTY2001/p/7632678.html

总结

以上是生活随笔为你收集整理的数学 砍树的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。