讲道理：这种题我是绝对不去（敢）碰的。比赛时被这个题坑了一把，对于我这种不A不罢休的人来说就算看题解也要得到一个Accepted。
这题网上有很多题解，我自己是很难做出来的，于是参考了一下思路，确实很niub的一个题。先记录下来将来回来也有个参考。
题意：有n个人，每个人有一定数量的硬币a[i]，每天将最富有的一个人的一枚硬币给最穷的那个人。求k天后最富有的人与最穷的人的差为多少。
思路：两遍二分啊，前所未见。因为k是固定的，我们先将所有人所能达到的上下界求出来，比如最穷的人的上界是sum/n，而最富有的人的下界不一定是sum/n，因为sum%n!=0，必有一个人多出1。我们二分所有富的人能达到下界，与穷的人能达到的上界，相减即为答案。
开始还纠结了一下为什么这样是对的，后来想想，在k之内增加与减少是一一对应的，只需单方判断与k的关系即可。
int n,m;
ll a[N];
int find(ll mid)
{
ll num=0;
for(int i=0; i<n; i++)
if(a[i]<mid) num+=mid-a[i];
if(num>m) return 0;
return 1;
}
int find1(ll mid)
{
ll num=0;
for(int i=n-1; i>=0; i--)
if(a[i]>mid) num+=a[i]-mid;
if(num>m) return 0;
return 1;
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
ll sum=0;
for(int i=0; i<n; i++)
{
scanf("%I64d",&a[i]);
sum+=a[i];
}
ll up=sum/n,down=up;
if(sum%n) down++;
ll ans1,ans2;
ll l=0,r=up;
while(r>=l)
{
ll mid=(l+r)/2;
if(find(mid))
{
ans1=mid;
l=mid+1;
}
else r=mid-1;
}
l=down,r=INF;
while(r>=l)
{
ll mid=(l+r)/2;
if(find1(mid))
{
ans2=mid;
r=mid-1;
}
else l=mid+1;
}
printf("%I64d\n",ans2-ans1);
}
return 0;
}
浑水摸鱼!111111