7-32 中位数 (10 分)
一个有 n 个整数的数组 a，n是一个奇数。
每次可以选择数组里的一个元素 ai 并把这个元素加上 1。
在至多 k 次操作之后，数组的中位数最大能变成多少。
输入格式:
多组输入
第一行两个整数 n,k(1≤n≤2×105,1≤k≤109)。
第二行 n 和整数 a1,a2,......,an。
输出格式:
k 次操作后数组的中位数。
输入样例:
1. 3 2 2. 1 3 5
结尾无空行
输出样例:
结尾无空行
1.
#include<iostream> #include<algorithm> using namespace std; const int MAX=2e5+10,N=1e10; int a[MAX],n,k; int find(int mid){ int s=0; for(int i=n/2;i<n;i++){ if(a[i]<mid){ s+=mid-a[i]; if(s>k)return 0; } }return 1; } int main(){ while(cin>>n>>k){ for(int i=0;i<n;i++)cin>>a[i]; sort(a,a+n); int l=0,r=N,ans; while(l<=r){ int mid=(l+r)/2; if(find(mid)){ ans=mid; l=mid+1; }else r=mid-1; }cout<<ans<<endl; } return 0; }
