3578. 最大中位数

（个人二分模板分析见主页）

$WA 代码$

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 200010;
int a[N], n, k;

int main(){
    scanf("%d%d", &n, &k);
    for(int i = 0; i < n; i ++ ){
        scanf("%d", &a[i]);
    }
    if(n == 1){
        printf("%d", a[0] + k);
    }
    else{
        sort(a, a + n);
        while(k > 0){
            for(int j = (n + 1) / 2; j < n; ){
                if(a[j - 1] > a[j]) j ++ ;
                k -- ;
                a[j - 1] ++ ;
                if(k == -1){
                    a[(n - 1) / 2] -- ;
                    break;
                }
            }
        }
        printf("%d", a[(n - 1) / 2]);
    }

    return 0;
}

分析：

代码时间复杂度为 $O(n \log n + k n)$ ，最坏情况下需要计算 $2\times 10^{14}$ 次，远远超过 $10^{8}$ 。故暴力只能过 $6/10$ 的数据，剩下的会 $TLE$ 。

$AC 代码$

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;

const int N = 200010;
int a[N];
int n, k;

// 检查中位数能否增加到x
bool check(LL x) {
    LL sum = 0;
    for (int i = n / 2; i < n; ++i) {
        if (a[i] < x) {
            sum += x - a[i]; // 计算增加到x需要的操作数
        }
    }
    return sum <= k;
}

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

    sort(a, a + n);
    LL l = a[n / 2], r = l + k; // 设置搜索范围
    while (l < r) {
        LL mid = l + (r - l + 1) / 2;
        if (check(mid)) l = mid; // 如果mid可行，尝试更大的值
        else r = mid - 1; // 否则尝试更小的值
    }

    printf("%lld\n", l);
    return 0;
}

分析：

此时的代码时间复杂度为 $O(n \log n + \log k n)$，即 $O(\log k n^{n + 1})$ ，最坏情况下需要计算约 $3.5\times 10^{6}$ 次，在合理范围内，故能通过。

优化核心是 $Binary Search$ 算法，把线性复杂度 $O(k n)$ 优化为对数复杂度 $O(\log k n)$，极大地提升了代码效率。

下面分析二分查找代码是怎么实现的：

• 首先，代码使用了左上型（左真型 & 向上取整）的二分查找模板，即：

    int bsearch_2(int l, int r)
    {
        while (l < r)
        {
            int mid = l + (r - l + 1) / 2;
            if (check(mid)) l = mid;
            else r = mid - 1;
        }
        return l;
    }

那么为什么不选择右真型或向下取整？

二分查找的核心其实是尝试，选择哪种类型重点在于向哪边尝试。题中要我们求尽可能大的中位数（求最大值问题），故最小的值肯定是 $true$ 的，而最大的则是 $false$ ，我们的 $target$ 则处于两者之间，
即符合：111111111 2 0000000000类问题（左真类问题）。
而选择向上取整而非向下取整是为了避免死循环问题，即确保在更新 l = mid 时，搜索区间能够收缩。这是因为当 l 和 r 相邻时，使用向上取整可以避免 mid 始终等于 l，从而避免死循环。

假设我们改用向下取整，即 mid = l + (r - l) / 2（或 mid = l + r >> 1），当 l 和 r 相邻时，mid 将等于 l。如果此时 check(mid) 返回 true，则会执行 l = mid，但由于 mid 等于 l，l 的值不会改变，导致搜索区间没有收缩，从而陷入死循环。

举个例子，假设 l = 3，r = 4，那么 mid = 3 + (4 - 3) / 2 = 3（向下取整）。如果 check(3) 返回 true，那么 l 将被更新为 3，即 l 的值没有改变，搜索区间没有收缩，导致死循环。
故选择向上取整还是向下取整的关键在于判断 l 和 r 会不会相邻，如果不会相邻那直接用位运算就完事了。

• 其次，bool 型函数 check 则无模板，需根据题目中的边界条件写判断语句。