9.14 砍树题解

　　这道题讲真还是挺友好的，纯暴力拿了50分。

　　当时我选择第一道题去搞他，第一反应是二分答案，毕竟理论上每次考试都有一道水题，然而仔细想想便可知不靠谱，然后就打了一个倒着搜的暴力，懵逼到结束。

　　这道题当时预测是一道数学题，然而看完题解发现，貌似是乱搞……我反正是不知道如何归类了。

　　假设我们已经知道当前的d，那么我们的答案也就出来了：

　　　num=∑（┍a[i]/d┑*d-a[i]）

　　那么只要num<=k就一定成立了，那么我们令sum=k+∑a[i]

　　那么我们会得到一个有趣的式子∑┍a[i]/d┑*d<=sum显然，┍a[i]/d┑是一个递减的分段函数，那么我们把它除过去，便可以知道当前d的最大可行取值。那么如何去找函数的每一段呢？我们设函数左端点为l，右端点为r,r=sum/(sum/l)，很神奇，但貌似不太好证，总之是对的。

　　

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#include<cmath>
#define N 105
using namespace std;
long long n,m;
long long a[N];
long long sum,ans;
int main()
{

scanf("%lld%lld",&n,&m);

for(int i=1;i<=n;i++)

{

scanf("%lld",&a[i]);

sum+=a[i];

}

sum+=m;

long long d=0;

while(1)

{

if(sum/(d+1)<=0)break;

d=sum/(sum/(d+1));

long long an=0;

for(int i=1;i<=n;i++)

{

long long tt=a[i]/d;

if(a[i]%d) tt++;

an+=tt*d;

}

if(an<=sum) ans=d;

}

printf("%lldn",ans);

return 0;
}