确认单调性的情况下用二分法枚举答案

因为要想mid变大，那么使用的k值最后一定也会变大，因此具有单调性

本题与 AcWing 1227. 分巧克力做法基本一致

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>

using namespace std;

typedef long long LL;

const int N = 200010, M = N << 1;

int n, k;
int a[N];

bool check(int mid)  //判断以mid做中位数时是否合法
{
    LL sum = 0;
    for(int i = n + 1 >> 1; i <= n; i ++)  //排序后要满足右边的数都大于mid，中位数才可以是mid
    {
        if(a[i] >= mid)  return true;  //还可以变得更大，往右区间查找
        sum += mid - a[i];  //不够就补成mid：变成mid还需要操作多少步
        if(sum > k)  return false;
    }
    return true;
}

int main()
{
    scanf("%d%d", &n, &k);
    for(int i = 1; i <= n; i ++)  scanf("%d", &a[i]);

    sort(a + 1, a + n + 1);

    LL l = 1, r = 2e9;
    while(l < r)
    {
        int mid = l + r + 1 >> 1;
        if(check(mid))  l = mid;
        else  r = mid - 1;
    }
    printf("%d\n", l);
    return 0;
}