B. Robin Hood
讲道理:这种题我是绝对不去(敢)碰的。比赛时被这个题坑了一把,对于我这种不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