中位數最大值的求法？
最大中位數
最大中位數
題目
給定一個由 nn 個整數組成的數組 aa，其中 nn 為奇數。
你可以對其進行以下操作：
選擇數組中的一個元素（例如 aiai），將其增加 11（即，將其替換為 ai+1ai+1）。
你最多可以進行 kk 次操作，并希望該數組的中位數能夠盡可能大。
奇數長度的數組的中位數是數組以非降序排序后的中間元素。
例如，數組 [1,5,2,3,5][1,5,2,3,5] 的中位數為 33。
輸入格式
第一行包含兩個整數 nn 和 kk。
第二行包含 nn 個整數 a1,a2,…,ana1,a2,…,an。
輸出格式。
輸出一個整數，表示通過操作可能得到的最大中位數。
數據范圍
對于 30%30% 的數據，1≤n≤51≤n≤5。
對于 100%100% 的數據，1≤n≤2×1051≤n≤2×105，1≤k≤1091≤k≤109，1≤ai≤1091≤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
算法
(二分) O(n(logn+logV))O(n(log?n+log?V))
二分答案，設當前二分的值為 x，考慮如何判斷中位數是否可以超過 x。
首先將數組 a 排序以方便判定。
記中位數的位置 p=(n+1)/2。
那么對于 a 中所有位置小于 p 的數，我們一定不需要修改這個數，因為如果我們將其中某個數加上了 d，那么把 d 加到一個位置 ≥p 的數上一定更優。
所以此時我們要做的事，就是判斷是否可以讓所有位置 ≥p 的數都 ≥x。
我們可以讓所有位置 ≥p 的數都 ≥x，求代價的最小值 v，若 v≤k，則答案可以超過 x。
枚舉所有位置 ≥p 的數 aj，如果這個數比 x 小，則將這個數修改成 x，將代價加入 v 即可。
時間復雜度
排序復雜度是 O(nlogn)O(nlog?n)。
二分復雜度是 O(nlogV)O(nlog?V)，其中 V 表示答案的值域。
故總復雜度為 O(n(logn+logV))O(n(log?n+log?V))。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 200005;
int n, k;
int a[N];
bool check(int mid) {
long long v = 0;
for (int i = n + 1 >> 1; i <= n; ++i)
if (a[i] < mid) v += mid - 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;
}
cout<<r;
return 0;
