题目题解

问题理解

给定一个长度为 $n$（奇数）的数组 $a$，每次操作可以将任意元素加 $1$，最多操作 $k$ 次。
求操作后可能的最大中位数。

---

第一步：排序

设排序后的数组为 $b_1 \le b_2 \le \dots \le b_n$。
中位数是 $b_{(n+1)/2}$，即中间元素。
我们只能通过增加元素来改变中位数，且只影响中间及后面的元素。

---

第二步：二分答案

由于答案具有单调性：若中位数可以达到 $x$，则比 $x$ 小的数也一定可以达到。
因此可以二分中位数 $x$。

对于给定的 $x$，我们需要将 $b_{(n+1)/2}, b_{(n+1)/2+1}, \dots, b_n$ 中所有小于 $x$ 的数提升到 $x$。
需要的操作次数为：

$$\text{need}(x) = \sum_{i = (n+1)/2}^{n} \max(0, x - b_i). $$

若 $\text{need}(x) \le k$，则 $x$ 可行；否则不可行。

---

第三步：二分范围

下界：当前中位数 $b_{(n+1)/2}$。
上界：$b_{(n+1)/2} + k$（因为最多将中位数增加 $k$）。

---

第四步：时间复杂度

• 排序：$O(n \log n)$。
• 每次二分检查 $O(n/2) = O(n)$。
• 二分次数 $O(\log (k)) \le O(\log 10^9) \approx 30$。
• 总复杂度 $O(n \log n + n \log k)$，满足 $n \le 2\times 10^5$。

---

代码实现

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

using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    
    sort(a.begin(), a.end());
    
    int mid = n / 2;  // 中位数下标（0-indexed）
    ll l = a[mid], r = a[mid] + k, ans = a[mid];
    
    while (l <= r) {
        ll x = (l + r) / 2;
        ll need = 0;
        for (int i = mid; i < n; i++) {
            if (a[i] < x) {
                need += x - a[i];
                if (need > k) break;
            }
        }
        if (need <= k) {
            ans = x;
            l = x + 1;
        } else {
            r = x - 1;
        }
    }
    
    cout << ans << "\n";
    
    return 0;
}

---

验证样例

输入：

3 2
1 3 5

排序后 $[1,3,5]$，中位数下标 $1$，$a[1]=3$。
二分：

• $x=5$，需要 $(5-3)+(5-5)=2 \le 2$，可行。
• $x=6$，需要 $3+1=4 > 2$，不可行。
  输出 $5$。

输入：

5 5
1 2 1 1 1

排序后 $[1,1,1,1,2]$，中位数下标 $2$，$a[2]=1$。
二分得 $x=3$，需要 $(3-1)+(3-1)+(3-2)=2+2+1=5 \le 5$，可行。
输出 $3$。

输入：

7 7
4 1 2 4 3 4 4

排序后 $[1,2,3,4,4,4,4]$，中位数下标 $3$，$a[3]=4$。
二分得 $x=5$，需要 $(5-4)+(5-4)+(5-4)+(5-4)=1+1+1+1=4 \le 7$，可行。
输出 $5$。

与题目输出一致。

---

总结

本题的关键在于：

1. 排序后，中位数只可能通过增加中间及后面的元素来提升。
2. 使用二分答案，检查将后半段所有小于 $x$ 的元素提升到 $x$ 所需操作数是否 $\le k$。
3. 时间复杂度 $O(n \log n + n \log k)$。