题目链接：https://nanti.jisuanke.com/t/41406
思路：如果k的天数足够大，那么所有水池一定会趋于两种情况：
① 所有水池都是一样的水位，即平均水位
② 最高水位的水池和最低水位的水池高度只相差一个高度，且最低水位一定是平均水位
如果k给了个限制：
我们当然需要先算出所有水池高度的平均值。
然后从低到高排序，二分小于平均值的水位，二分高于平均值的水位，
然后判断二分的预期值需要的天数是否小于等于k。然后二分找出最低水位的最大值，
最高水位的最小值，两者相减就是答案了。
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <map>
#define rep(i,j,k) for(int i = (j); i <= (k); ++i)
#define per(i,j,k) for(int i = (j); i >= (k); --i)
#define rep__(i,j,k) for(int i = (j); i < (k); ++i)
#define per__(i,j,k) for(int i = (j); i > (k); --i)
#define inf 1e9
using namespace std;
typedef long long LL;
const int N = ; int arr[N],k,n;
LL sum,ave; bool check(int mid,int choice){
int sum = ;
if(choice == ){ //大于平均值的
rep(i,,n){
if(arr[i] >= mid) break;
sum += (mid - arr[i]);
}
}
else{ //小于平均值的
per(i,n,){
if(arr[i] <= mid) break;
sum += (arr[i] - mid);
}
} if(sum <= k) return true;
else return false;
} int main(){ while(~scanf("%d",&n)){
sum = ;
scanf("%d",&k);
rep(i,,n){
scanf("%d",arr + i);
sum += arr[i];
} sort(arr + ,arr + + n);
ave = sum / n; int l_end,r_start; //低于平均值的最大水位，高于平均值的最小水位
l_end = ave;
sum % n == ? r_start = ave : r_start = ave + ; //是否能平分 int ans_1,ans_2;
int l = arr[];//左边界
int r = l_end;//右边界
int mid;
while(l <= r){
mid = (l + r) >> ;
if(check(mid,)){
ans_1 = mid;
l = mid + ;
}
else r = mid - ;
} l = r_start;//左边界
r = arr[n];//右边界
while(l <= r){
mid = (l + r) >> ;
if(check(mid,)){
ans_2 = mid;
r = mid - ;
}
else l = mid + ;
} printf("%d\n",ans_2 - ans_1);
} getchar();getchar();
return ;
}