最大化中位数

二分

算法思路

    首先对数组排序,中间的就是中位数.为了让中位数最大,我们的k次操作一定都是用在中位数及其之后
的所有元素上,让他们满足单调性.因为用在前面数字需要更多的操作次数.
    问题的结果具有单调性(->二分性).(咋比赛时没想到)中位数越大,需要的操作次数越多.所以存在一个
mid,<=mid的中位数满足条件,反之不满足条件.用二分法判断.

时间复杂度

排序 + 二分枚举 nlogn + nlogn

C++ 代码

#include<cstdio>
#include<algorithm>

using namespace std;

typedef long long ll;

const int N = 2e5 + 10;

int n, k;
int a[N];

bool check(int mid)
{
    ll res = 0;//a可能取到1e9 操作次数可能会溢出int
    for( int i = n/2; i < n; i++ )
        if( a[i] < mid )    
            res += mid - a[i]; //满足单调性至少让a[i]和中位数一样大
    return res <= k; //满足操作数小于k
}

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

    sort(a,a+n);

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

    return 0;
}