盲蛋

NC229580. 盲蛋

描述

某天阿祥搭乘休伯利安抵达了一个奇怪的世界泡，在这里他很幸运地碰到了识宝的小摊，他很想购买一些崩坏兽盲蛋回去给休伯利安的各位女武神玩。识宝表示崩坏兽盲蛋的售卖规则非常简单：每次她会给出n个福袋，每个福袋里有 $a_i（1\leq a_i \leq 10^9）$ 个盲蛋，开局你只需要支付648就可以随机获得k个盲蛋，然后你需要把这k个盲蛋分别放入任意福袋中（必须用完），最后获得这n个福袋中盲蛋数量的中位数个盲蛋。识宝修改了阿祥意识，他现在只会阿巴阿巴……，现在请聪明的你帮助阿祥，帮他算出最多能获得多少个盲蛋。

输入描述

第一行包含两个整数n $（1\leq n \leq 2*10^5，且n为奇数）$ 和k $（1\leq k \leq 10^9）$ 。

第二行包含n个整数 $a_1, a_2, ..., a_n$ （用空格隔开）。

输出描述

输出一个整数，表示阿祥能获得的盲蛋的最大数量。

示例1

输入:

3 2
1 3 5

输出:

示例2

输入:

7 5
4 1 2 4 3 4 4

输出:

说明:

每个福袋初始盲蛋数量为：4 1 2 4 3 4 4

开局手中有5个盲蛋，分别给数量是4的福袋中放入1个盲蛋，最后1个随便放入一个福袋：5 1 2 5 3 5 6

其中位数为5，所以最终答案为5。

上次编辑到这里，代码来自缓存点击恢复默认模板

Python3 解法, 执行用时: 932ms, 内存消耗: 28416K, 提交时间: 2021-11-23 15:28:14

a = [0]
def check (x , k , n):
    cost = 0
    for i in range(n // 2 + 1 , n + 1):
        cost += max(0 , x - a[i])
    return cost <= k

n , k = map(int, input().split())

a += list(map(int, input().split()))
a.sort()
l = 0
r = int(2e9)
while l <= r:
    mid = l + r >> 1
    if check(mid, k, n): l = mid + 1
    else: r = mid - 1
print(r)

C++ 解法, 执行用时: 57ms, 内存消耗: 1160K, 提交时间: 2021-11-14 14:38:42

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

int n,k;

int main(){
    cin >> n >> k;
    vector<int> a(n);
    for(int &x : a) cin >> x;
    sort(a.begin(),a.end());
    int l = n/2,r = n/2+1;
    LL x = a[l]+k;
    while(r < n && a[r] < x/(r - l)) x += a[r++];
    cout<<x/(r-l);
    return 0;
}