The Preliminary Contest for ICPC Asia Shenyang 2019 F. Honk's pool ( 模拟）

F. Honk’s pool

As we all know, Honk has $n$ pools, numbered as $1$ ~ $n$ . There is aia_iai​ liters water in the $i$-th pool. Every day, Honk will perform the following operations in sequence.

1. Find the pool with the most water (If there are more than one, choose one at random) and take one liter of water.

2. Find the pool with the least water (If there are more than one, choose one at random) and pour one liter of water into the pool.

3. Go home and rest (Waiting for the next day).

Please calculate the difference between the amount of water in the pool with the most water and the amount of water in the pool with the least water after the $k$ days.

Input

The input consists of multiple test cases. The input is terminated by the end of file.The number of data sets will not exceed 40

The first line of each test case contains two integers $n$ and $k$, which indicate the number of pools and the number of days to operate the pool.

The second line of each test case contains $n$ integers, and the $i$-th number represent aia_iai​ indicating the initial amount of water in the $i$-th pool.

$1\le n\le 500000$, 1≤k≤1091 \le k \le 10^91≤k≤109, 1≤ai≤1091 \le a_i \le 10^91≤ai​≤109.

Output

For each test case, print one line containing the answer described above.

AC Code：

#include using namespace std;const int maxn = 500010;
typedef long long ll;
ll k, a[maxn], s, _remainder, n;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);while (cin >> n >> k) {s = 0;for (int i = 1; i <= n; ++i) {cin >> a[i];s += a[i];}_remainder = s % n;sort(a + 1, a + n + 1);ll tempK = k, currMin = 0x3f3f3f3f, currMax = -1;for (ll i = n; i > 1 && tempK > 0; --i) {if ((a[i] - a[i - 1]) * (n - i + 1) <= tempK) {tempK -= (a[i] - a[i - 1]) * (n - i + 1);currMax = a[i - 1];} else {currMax = a[i] - tempK / (n - i + 1);break;}}tempK = k;for (ll i = 1; i < n && tempK > 0; ++i) {if ((a[i + 1] - a[i]) * i <= tempK) {tempK -= (a[i + 1] - a[i]) * i;currMin = a[i + 1];} else {currMin = a[i] + tempK / i;break;}}
//        cout << currMin << "  " << currMax << endl;cout << (currMax > currMin ? currMax - currMin : (_remainder == 0 ? 0 : 1)) << "\n";
//        cout << flush;}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！