算法
(二分) $O(n (\log n + \log V))$
二分答案，设当前二分的值为 $x$，考虑如何判断中位数是否可以超过 $x$。
首先将数组 $a$ 排序以方便判定。
记中位数的位置 $p = \displaystyle \frac {n + 1} 2$。
那么对于 $a$ 中所有位置小于 $p$ 的数，我们一定不需要修改这个数，因为如果我们将其中某个数加上了 $d$，那么把 $d$ 加到一个位置 $\geq p$ 的数上一定更优。
所以此时我们要做的事，就是判断是否可以让所有位置 $\geq p$ 的数都 $\geq x$。
我们可以让所有位置 $\geq p$ 的数都 $\geq x$，求代价的最小值 $v$，若 $v \leq k$，则答案可以超过 $x$。
枚举所有位置 $\geq p$ 的数 $a _ j$，如果这个数比 $x$ 小，则将这个数修改成 $x$，将代价加入 $v$ 即可。
时间复杂度
排序复杂度是 $O(n \log n)$。
二分复杂度是 $O(n \log V)$，其中 $V$ 表示答案的值域。
故总复杂度为 $O(n (\log n + \log V))$。
C++ 代码
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 200005;
int n, k;
int a[N];
bool check(int x) {
long long v = 0;
for (int i = n + 1 >> 1; i <= n; ++i)
if (a[i] < x) v += x - a[i];
else break;
return v <= k;
}
int main() {
cin >> n >> k;
for (int i = 1; i <= n; ++i) cin >> a[i];
sort(a + 1, a + n + 1);
int l = 0, r = 2e9, mid;
while (l < r) {
mid = 1ll + l + r >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
printf("%d\n", r);
return 0;
}
定义l和r的时候不能让l等于原本数组的中位数，让r等于原本的中位数加k吗？
tql
为什么r要赋值为2e9
假设 $n = 1, a _ 1 = 10 ^ 9, k = 10 ^ 9$，此时最优解（唯一解）即为将 $k$ 加到 $a _ 1$ 上，故答案为 $2 \times 10 ^ 9$。
想问一下为什么这里要1+l+r>>1不能用l+r>>1;
这个当成模板就好了。具体的话，因为如果写
l+r>>1，那么当r=l+1且check(l)的值为真时，mid就会取l，然后因为check(mid)是真，就会执行l=mid，这相当于什么都没干，之后的循环就会一直执行上述操作，导致死循环。懂了谢谢，所以会tle
抽风姐姐 为什么这里
需要加判定呢，感觉不判定也可以判断出正确的结果
但是是错的qaq
您指的是判定
a[i] < x嘛？因为如果a[i] > x，那么此时不需要修改a[i]，因此不需要执行这步。如果a[i] > x时执行了v += x - a[i]有可能会使v变小，得到错误的v。这句“抽风姐姐”叫的。。。
这题没必要二分吧，顺序遍历就行了；二分判定的时候也进行了遍历复杂度反而更高了
是的。这个做法是我打比赛时写的做法。直接遍历的做法不是很好写，所以就写了二分。
为啥k输入后就没用过了？？
check里面写错了，v<=k写成v<=m了。已修正。check函数那里的v<=m是故意写的吗？
因为l=mid表示的是v<=m
不应该是v<=k吗
写错了，打比赛的时候用的是
v<=m。已修正。大佬你好，为什么要1ll而不是1啊
mid = 1ll + l + r >> 1;
因为 l + r 可能会溢出
1ll+l+r会先转成long long类型再操作。若不转成long long类型，最坏情况下答案是$2 \times 10 ^ 9$，那么二分中就会出现l接近 $2 \times 10 ^ 9$，r总等于 $2 \times 10 ^ 9$ 的情况，此时l + r会接近 $4 \times 10 ^ 9$，会超过int类型的上限。噢，懂了，谢谢大佬
orz
抽风大佬yyds
Orz
orz
orz