题目描述

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

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

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

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

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

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

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

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

数据范围
对于 30% 的数据，1≤n≤5。
对于 100% 的数据，1≤n≤2×105，1≤k≤109，1≤ai≤109。

样例

输入样例1：
3 2
1 3 5
输出样例1：
5
输入样例2：
5 5
1 2 1 1 1
输出样例2：
3
输入样例3：
7 7
4 1 2 4 3 4 4
输出样例3：
5

算法1

(二分枚举) $O(nlog(n))$

时间复杂度

参考文献

python3 代码

[n, k] = [int(x) for x in input().split()]
nums = [int(x) for x in input().split()]

nums.sort()
n = len(nums)

def check(mid: int) -> bool:
    need = 0
    for i in range(n//2, n):
        if mid > nums[i]:
            need += (mid - nums[i])
        else:
            break
    return need <= k

L = 0
R = 10 ** 10
while L < R:
    mid = (L + R + 1) // 2;
    if check(mid) == True:
        L = mid
    else:
        R = mid - 1

print(L)

C++ 代码

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int n;   cin >> n;
    int k;   cin >> k;
    int nums[n];
    for (int i = 0; i < n; i ++)
        cin >> nums[i];
    sort(nums, nums + n);

    std::function<bool(int)> check = [&](int mid)
    {
        long long need = 0;
        for (int i = n / 2; i < n; i ++)
        {
            if (mid > nums[i])
                need += (mid - nums[i]);
            else
                break;
        }
        return need <= k;
    };

    int L = 1;
    int R = 2e9;
    while(L < R)
    {
        int mid = ( (long long)L + R + 1 ) / 2;
        if (check(mid) == true)
            L = mid;
        else
            R = mid - 1;
    }

    cout << L << endl;

    return 0;

}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla