最大中位數

最大中位數

題目

給定一個由 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;