题目描述

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

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

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

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

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

样例

输入样例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

C++ 代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int cmp(const void *a,const void *b){
return *(ll int*)a-*(ll int *)b;
}
int main(){
  ll int n,k;
  ll int a[200000];
  scanf("%lld%lld",&n,&k);
  for(int i=0;i<n;i++){
    scanf("%lld",&a[i]);
  }
  qsort(a,n,sizeof(a[1]),cmp);
  int mid=n/2;
  for(int i=0;k!=0;i++){
    int cnt=a[mid+i]-a[mid];
    if(k>=(cnt*i)){k-=(cnt*i);a[mid]=a[mid+i];}
    else{
      a[mid]+=k/i;
      k=0;
      break;
    }
    if(mid+i+1==n){
      a[mid]+=k/(i+1);
      break;
    }
  }
  printf("%lld",a[mid]);
  return 0;
}