Minimizing Difference 【思维】

题目链接：

https://vjudge.net/contest/336389#problem/B

题目大意：

给出一个长度为n的数列以及操作次数k。k的范围为1e14。每次操作都可以选择给任意一个数加1或者减1。问k次操作后，数列中最大值与最小值的差值最小是多少。

解题思路：

1.可以用二分

2.思维，对数组进行排序，同时计算前后两个方向。具体看代码：

#include<stdio.h>
#include<algorithm>
typedef long long ll;
const int MAXN = 1e5 + 100;
using namespace std;

ll a[MAXN];
ll n, k, temp, ans;

int main()
{
    scanf("%lld%lld", &n, &k);
    for(int i = 1; i <= n; i ++)
        scanf("%lld", &a[i]);
    sort(a + 1, a + 1 + n);
    for(int i = 1; i <= n / 2; i ++)
    {
        int j = n - i + 1;
        temp = (a[i + 1] - a[i] + a[j] - a[j - 1]) * i; //将前i个都变成a[i + 1]以及将后i个全变成a[j]所需要的操作次数 
        if(temp <= k)
            k -= temp;
        else
        {
            ans = a[j] - a[i] - k / i; //剩余操作次数可否使某一边都作贡献 
            break;
        }
    }
    printf("%lld
", ans);
    return 0;
}