题目描述

给定一个由 n 个整数组成的数组 a，其中 n 为奇数。

你可以对其进行以下操作：

选择数组中的一个元素（例如 ai），将其增加 1（即，将其替换为 ai+1）。
你最多可以进行 k 次操作，并希望该数组的中位数能够尽可能大。

奇数长度的数组的中位数是数组以非降序排序后的中间元素。

例如，数组 [1,5,2,3,5] 的中位数为 3

输入格式

第一行包含两个整数 n 和 k。

第二行包含 n 个整数 a1,a2,…,an。

输出格式

输出一个整数，表示通过操作可能得到的最大中位数。

数据范围

对于 30% 的数据，1≤n≤5。
对于 100% 的数据，1≤n≤2×105，1≤k≤109，1≤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

算法1

(贪心+左右指针) $O(nlog n)$

这道题首先我们将整个数组
然后我们定义一个左右指针l,r
定义n=数组大小-1

左指针l指向中位数所在下标
右指针r指向中位数右边(包括中位数本身)最后一个等于中位数的下标 (l<=r<=n)

这样我们的左右指针就是一个区间

每次循环我们都把区间内所有的数 +1 这样我们的中位数就 +1 同时 k要减去 r-l+1

当 k==0 或者 k<r-l+1 (不够区间内所有值都+1) 的时候循环停止 此时的中位数就是我们要求的中位数

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e6+10;

typedef long long LL;

int n,k;
int a[N];

int seekR(int q[],int r){  //寻找右端点
    int res=r;
    int flag=0;
    for(int i=r;i<=n;i++){
        if(q[r]==q[i]){
            continue;
        }
        else{
            flag=1;
            res=i-1;
            break;
        }
    }
    if(flag==0){
        res=n;
    }

    return res;

}


int main(){
    cin>>n>>k;

    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    if(n==1){
        cout<<k+a[1]<<endl;
        return 0;
    }
    sort(a+1,a+n+1);


    int l=(n/2)+1;
    int r=seekR(a,l);
    int num=a[l];

    while(k && k>=r-l+1){

        num++;
        k-=r-l+1;
        a[r]=num;
        r=seekR(a,r);
    }

    cout<<num<<endl;

    return 0;
}

算法2

(二分) $O(nlong n)$

当时做题的时候并没有想到二分
这种方法是参考别人的

我们每次从 1 到 2e9 中二分查找答案
这里解释一下右端点为什么是 2e9 ：
因为题目给出的范围 1<=k<=1e9,1<=w[i]<=1e9 如果说k==1e9 n==1 w[0]== 1e9 的时候
要找的答案就是1e9+1e9 也就是我们右端点的最大值

参考代码

https://www.acwing.com/activity/content/code/content/1300036/

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

typedef long long LL;

using namespace std;

const int N = 2e5+10;

int n,k;
int w[N];

bool check(int mid){
    LL res=0;
    for(int i=n/2;i<n;i++){
        if(w[i]<mid)
            res+=mid-w[i];
    }
    return res<=k;
}

int main(){
    cin>>n>>k;
    for(int i=0;i<n;i++) scanf("%d",&w[i]);
    sort(w,w+n);
    int l=0,r=2e9;
    while(l<r){
        int mid=(LL)l+r+1>>1;
        if(check(mid)) l=mid;
        else r=mid-1;
    }
    printf("%d\n",r);
    return 0;
}