Codeforces 671B. Robin Hood 二分

We all know the impressive story of Robin Hood. Robin Hood uses his archery skills and his wits to steal the money from rich, and return it to the poor.

There are n citizens in Kekoland, each person has ci coins. Each day, Robin Hood will take exactly 1 coin from the richest person in the city and he will give it to the poorest person (poorest person right after taking richest's 1 coin). In case the choice is not unique, he will select one among them at random. Sadly, Robin Hood is old and want to retire in k days. He decided to spend these last days with helping poor people.

After taking his money are taken by Robin Hood richest person may become poorest person as well, and it might even happen that Robin Hood will give his money back. For example if all people have same number of coins, then next day they will have same number of coins too.

Your task is to find the difference between richest and poorest persons wealth after k days. Note that the choosing at random among richest and poorest doesn't affect the answer.

Input

The first line of the input contains two integers n and k (1 ≤ n ≤ 500 000, 0 ≤ k ≤ 109) — the number of citizens in Kekoland and the number of days left till Robin Hood's retirement.

The second line contains n integers, the i-th of them is ci (1 ≤ ci ≤ 109) — initial wealth of the i-th person.

Output

Print a single line containing the difference between richest and poorest peoples wealth.

Examples

input

4 1
1 1 4 2

output

input

3 1
2 2 2

output

Note

Lets look at how wealth changes through day in the first sample.

[1, 1, 4, 2]
[2, 1, 3, 2] or [1, 2, 3, 2]

So the answer is 3 - 1 = 2

In second sample wealth will remain the same for each person.

题目链接：http://codeforces.com/problemset/problem/671/B

题意：有n个数，k次操作。每次操作都把最大值-1，最小值+1。直到k次操作完，或最大值等于最小值操作结束。输出最后最大值与最小值得差值

思路：n个数向平均数靠近。靠近程度与k有关。二分一个符合情况的最大值max。那么就要把比max大的数补给比max小的数。假设大kk，小tt，如果kk<=k&&tt>=kk说明max太大；二分一个符合情况的最小值min。那么就要把比min大的数补给比min小的数。假设小kk，大tt，如果kk<=k&&tt>=kk说明min太小。输出差值。

代码：

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 5e5+100, mod = 1e9 + 7, inf = 0x3f3f3f3f;
int c[MAXN];
int n,k;
int check1(int Max)
{
    int i;
    __int64 kk=0,tt=0;
    for(i=0; i<n; i++)
    {
        if(c[i]>Max)
            kk+=(c[i]-Max);  ///统计比当前答案大得可以拿出多少
        else
            tt+=(Max-c[i]);  ///统计比当前答案小的一共得到多少
    }
    if(kk<=k&&tt>=kk) return 1;///多的数必须小于天数，并且小的必须大于多的，说明答案太大了
    return 0;
}
int check2(int Min)
{
    int i;
    __int64 kk=0,tt=0;
    for(i=0; i<n; i++)
    {
        if(c[i]<Min)
            kk+=(Min-c[i]);  ///比当前答案小的总数
        else
            tt+=(c[i]-Min);  ///比当前答案大的总数
    }
    if(kk<=k&&tt>=kk) return 1; ///小的总数必须小于天数，大的总数大于小的总数，说明当前的答案太小
    return 0;
}
int main()
{
    int i;
    scanf("%d%d",&n,&k);
    for(i=0; i<n; i++)
        scanf("%Id",&c[i]);
    sort(c,c+n);
    int Max=c[n-1],Min=c[0];
    int r=Max,l=Min;
    while(l<=r)
    {
        int mid=(l+r)/2;
        if(check1(mid))
        {
            r=mid-1;
            Max=mid;
        }
        else l=mid+1;
    }
    r=c[n-1];
    l=c[0];
    while(l<=r)
    {
        int mid=(l+r)/2;
        if(check2(mid))
        {
            l=mid+1;
            Min=mid;
        }
        else r=mid-1;
    }
    printf("%d
",Max-Min);
    return  0;
}

View Code

I am a slow walker,but I never walk backwards.