有n(<=500000)个人有各自的财富,Robin Hood要劫富济贫,每次把最富有的那个人的财富抢去1,加在最穷的那个人的财富里,但是一共只能抢有限次数,问最后最富有的那个人和最穷的那个人财富差的最小值。
要让最富有与最穷的差值最小,也就是要让一个最大值最小,最小值最大,用最大值最小-最小值最大那么就是最小，那么求这两个值就可以用二分.
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define LL long long
using namespace std;
const int maxn = 500010;
LL n,k,a[maxn],pre[maxn],sum,mini,maxi,ave;
int checkp(LL x) {
int p = lower_bound(a+1,a+n+1,x)-a-1;
if(p*x-pre[p] > k)return 0;//***
else return 1;
}
int checkr(LL x) {
int p = upper_bound(a+1,a+1+n,x)-a;
if(pre[n]-pre[p-1]-(n-p+1)*x > k)return 0;//*****
else return 1;
}
int main() {
scanf("%I64d%I64d",&n,&k);
for(int i = 1; i <= n; ++i)scanf("%I64d",&a[i]);
sort(a+1,a+n+1);
for(int i = 1; i <= n; ++i) {
sum += a[i];
pre[i] = pre[i-1]+a[i];
}
ave = sum / n;
LL l = a[1],r = ave+1;
while(l+1 < r) {
LL mid = (l+r)/2;
if(checkp(mid))l = mid;
else r = mid;
}
mini = l;
l = ave,r = a[n];if(sum%n)++l;
while(l < r) {
LL mid = (l+r)/2;
if(checkr(mid))r = mid;
else l = mid+1;
}
maxi = l;
printf("%I64d\n",maxi-mini);
return 0;
}
codeforces 671B (二分) - xgtao -
原文：http://www.cnblogs.com/xgtao984/p/5720165.html