题目描述

给定一个由 n 个整数组成的数组 a，其中 n 为奇数。

你可以对其进行以下操作：

选择数组中的一个元素（例如 ai），将其增加 1（即，将其替换为 ai+1）。
你最多可以进行 k 次操作，并希望该数组的中位数能够尽可能大。

奇数长度的数组的中位数是数组以非降序排序后的中间元素。

例如，数组 [1,5,2,3,5][1,5,2,3,5] 的中位数为 3。

输入格式
第一行包含两个整数 n 和 k。

第二行包含 n 个整数 a1,a2,…,an。

输出格式。
输出一个整数，表示通过操作可能得到的最大中位数。

样例

7 7
4 1 2 4 3 4 4

算法1

其实这个题没必要用到二分。
打个比方，假设一组数据（已排序完）：
1 3 6 8 10 12 15
如果我们模拟一下，那我们肯定会直接加在中位数上：
1 3 6 9 10 12 15
1 3 6 10 10 12 15
这里我们发现再加就超了，于是我们会在中位数后第一个数加1：
1 3 6 10 11 12 15
这时我们又可以加在中位数了。
直到：
1 3 6 12 12 12 15
这时我们发现又不能再加了，此时我们需要对中位数后第二个数加1：
1 3 6 12 12 13 15
再重复上述步骤。

回到题目，由于加数是有限制的，而且数据范围偏大，我们不能像上述过程那样暴力模拟，
我们可以考虑一下每次直接加的数是多少。
在上面那个例子中，假设中位数是第M个数，我们可以把第M个数的数值直接加到第M+1个数的数值那么大，
再把第M个数和第M+1个数的数值直接加到M+2那么大，以此类推。

我们最先还是要排序。
令数加数限制为k，
每次我们要加多少，k就减多少，
对于第N个数，要加( 当前数的大小 - 前一个数的大小 ) * (N ~ mid)，
如果( 当前数的大小 - 前一个数的大小 )是负数时，就是k小了，不能加到N的大小，
但我们还是将k的剩余值均分给前（N-1 ~ mid),于是让k = k/（N-1 ~ mid),
“第N-1个数的数值大小 + k”就是题目的答案，就是这么简单。

这个时间复杂度大概是O(nlogn)，主要是排序的时间。

时间复杂度

参考文献

C++ 代码

#include<bits/stdc++.h>
using namespace std;
int n , k , N[200000+5];
int main(){
    scanf("%d%d", &n , &k);
    for(int i=1 ; i<=n ; i++){
        scanf("%d", &N[i]);
    }
    sort(&N[1] , &N[n+1]);
    int i=n/2+2;
    for( ; i<=n ; ){
        int a=N[i]-N[i-1];
        if(k-a*(i-n/2-1)<=0)break;//判断能不能加到第N个数
        k = k-a*(i-n/2-1);//减去加数
        i++;
    }
    printf("%d", N[i-1]+k/(i-n/2-1));
    return 0;
}