中位数最大值的求法

中位数最大值的求法？

最大中位数

最大中位数

题目

给定一个由 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

#include

#include

#include

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<

return 0;