14081: 【原4081】侠盗罗宾

题目

题目描述

author: Will 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4081

Description

我们都知道侠盗罗宾的故事，罗宾总是用他的智慧劫富济贫。

在 P 城有 n 个市民，每个人有 \(c _i\) 枚硬币。罗宾每天会从 P 城最富的人那里偷出 1 枚硬币送给 P 城最穷的人 。如果这样的选择不唯一，他会随机挑一个符合条件的人。然而，我们的老罗宾很快就要退休了，他决定在剩下的 k 天里尽可能多帮助一些市民。

如果最富的人在被偷走硬币后变成了最穷的人，则他的钱会被还回到他的手里。例如，如果所有的人都有一样数量的硬币，一天后他们的硬币数量仍然会是一样的。

你的任务就是计算出 k 天之后 P 城中最富的人和最穷的人间的财富差(取绝对值)。

Input

第一行包含两个整数 n 和 k ( \(1 \le n \le 500 000, 0 \le k \le 10^9\) )。

第二行包含 n 个整数， 第 i 个数代表第 i 个市民最初拥有的硬币数 \(c _i\) ( \(1 \le c_i \le 10^9\) )。

Output

一行， k 天之后最穷的人和最富的人之间财富的绝对差值。

Examples

input

4 1 
1 1 4 2

output

2

input

3 1 
2 2 2

output

0

Hints

这道题可以考虑二分。

FineArtz's solution

/* 侠盗罗宾 */
#include <iostream>
#include <map>
#include <algorithm>
using namespace std;

int n, k;
map<int, long long> w;

int main(){
    cin >> n >> k;
    int maxx = 0, minn = 1000000005;
    long long sum = 0;
    for (long long i = 1; i <= n; ++i){
        int t;
        cin >> t;
        ++w[t];
        maxx = max(maxx, t);
        minn = min(minn, t);
        sum += t;
    }
    long long p = 0, pp = 0, r = 0, rr = 0;
    for (auto i = w.begin(); ; ++i){
        if (pp + i->second > n / 2) break;
        pp += i->second;
        p += i->first * i->second;
    }
    for (auto i = w.end(); ; --i){
        if (i == w.end()) continue;
        if (rr + i->second > n / 2) break;
        rr += i->second;
        r += i->first * i->second;
    }
    if (r - p <= 2 * k){
        if (sum % n == 0)
            cout << 0 << endl;
        else
            cout << 1 << endl;
        return 0;
    }
    int kk = k, mp = minn, tp = w[minn];
    for (auto i = w.begin(); ; ++i){
        if (i == w.begin()) continue;
        if ((i->first - mp) * tp > kk){
            mp += kk / tp;
            break;
        }
        kk -= (i->first - mp) * tp;
        mp = i->first;
        tp += i->second;
    }
    int mr = maxx, tr = w[maxx];
    kk = k;
    for (auto i = w.end(); ; --i){
        if (i == w.end()) continue;
        if (i->first == maxx) continue;
        if ((mr - i->first) * tr > kk){
            mr -= kk / tr;
            break;
        }
        kk -= (mr - i->first) * tr;
        mr = i->first;
        tr += i->second;
    }
    cout << mr - mp << endl;
    return 0;
}