Link: Codeforces Round 577 (Div. 2) - C

Maximum Median

Description:
You are given an array a of n integers, where n is odd. You can make the following operation with it:

Choose one of the elements of the array (for example ai) and increase it by 1 (that is, replace it with ai+1).
You want to make the median of the array the largest possible using at most k operations.

The median of the odd-sized array is the middle element after the array is sorted in non-decreasing order. For example, the median of the array [1,5,2,3,5] is 3.

Input
The first line contains two integers n and k (1≤n≤2⋅1e5, n is odd, 1≤k≤1e9) — the number of elements in the array and the largest number of operations you can make.

The second line contains n integers a1,a2,…,an (1≤ai≤1e9).

Output
Print a single integer — the maximum possible median after the operations.

Examples
input
3 2
1 3 5
output
5
input
5 5
1 2 1 1 1
output
3
input
7 7
4 1 2 4 3 4 4
output
5
Note
In the first example, you can increase the second element twice. Than array will be [1,5,5] and it's median is 5.

In the second example, it is optimal to increase the second number and than increase third and fifth. This way the answer is 3.

In the third example, you can make four operations: increase first, fourth, sixth, seventh element. This way the array will be [5,1,2,5,3,5,5] and the median will be 5.

Problem solving:
这道题的意思就是给你一组数，然后给你一个k值，你可以随意地把k分配到每一个数上，现在要求你分完之后得到最大的的中位数的值。我是从二分的tag找到的这道题。一开始毫无思路。后来发现，首先前半部分的数对答案是不会有影响的，所以我们只需要处理中间的数以及他后面的数就行。所以先sort一下，然后从中间那个数开始进行二分。二分的最小值就是中间值的大小，二分的最大值就是中间的值加上k。二分中check的时候我们需要从中间开始遍历每一个数，累加每一个数大于mid的值的多少，最后跟k比较。如果k小于那个累加的值，说明这个mid达不到。反之说明可以。

二分是真的巧妙
Code:

#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 2e5 + 10;
typedef long long ll;
ll        a[maxn], n, k, mid;
bool check(ll x)
{
    ll s = 0;
    for (ll i = mid; i <= n; i++)
    {
        if (a[i] < x)
            s += (x - a[i]);
        if (k < s)
            return 0;
    }
    return 1;
}
int main()
{
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    sort(a + 1, a + n + 1);
    mid = (1 + n) >> 1;
    ll l, r;
    l = a[mid], r = a[mid] + k;
    while (l <= r)
    {
        ll m = (l + r) >> 1;
        if (check(m))
        {
            l = m + 1;
        }
        else
            r = m - 1;
    }
    cout << l - 1 << endl;
}
赏