题目链接:
Codeforces #352 Div2 D Robin Hood
题意:
给出n个数,每次可以将最大数-1,最小数+1,问K次后最大数和最小数之差?
分析:
二分查找k次最大数的最小值y和最小数的最大值x.
如果x>=y并且这些数的和sum能被n整除则ans为0;
如果x>=y并且这些数的和sum不能被n整除则ans为1.
否则(x < y),ans为y-x.
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <climits>
#include <cmath>
#include <ctime>
#include <cassert>
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
typedef long long ll;
const int MAX_N = 500010;int n, k;
ll data[MAX_N];bool check1(ll y)
{ll kk = k;for(int i = n - 1; i >= 0; i--){if(data[i] <= y ) return true;kk -= (data[i] - y);if(kk < 0) return false;}return true;
}ll binsearch1() //最大值的最小值
{ll high = data[n - 1], low = data[0];while(high > low){ll mid = (high + low) >> 1;if(check1(mid)) high = mid;else low = mid + 1;//cout << "high = " << high << " low = " << low << endl;}return high;
}bool check2(ll x)
{ll kk = k;for(int i = 0; i < n; i++){if(data[i] >= x) return true;kk -= (x - data[i]);if(kk < 0) return false;}return true;
}ll binsearch2() //最小值的最大值
{ll high = data[n - 1], low = data[0];while(high > low + 1){ ll mid = (high + low) >> 1;if(check2(mid)) low = mid;else high = mid - 1;//cout << "high = " << high << " low = " << low << endl;}if(check2(high)) return high;return low;
}int main()
{IOS;while(cin >> n >> k){ll sum = 0;for(int i = 0; i < n; i++){cin >> data[i];sum += data[i];}sort(data, data + n);ll y = binsearch1();ll x = binsearch2();//cout << "y = " << y << " x = " << x << endl;if(x >= y) {if(sum % n == 0) cout << 0 << endl;else cout << 1 << endl;} else cout << y - x << endl; }return 0;
}