题意：就是给一n(奇数)个元素数组，可以对它的元素执行k次+1操作，递增排序，求中位数最大是多少。
那我们在排完序之后，中位数前的元素可以不管它，只要对中位数后的操作就行，我们要判断和中位数相等的元素有几个，再用k减去它，循环一下，当k小于0时没的减了，也就是数组元素不能再加了时跳出来。
附ac代码：
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<cmath> 5 #include<algorithm> 6 #define ma (int)2e5+1 7 using namespace std; 8 int main(){ 9 int n,k,a[ma]; 10 cin>>n>>k; 11 for(int i=1;i<=n;i++){ 12 cin>>a[i]; 13 } 14 if(n==1){ 15 cout<<a[1]+k; 16 return 0; 17 } 18 sort(a+1,a+1+n); 19 int i,l=0,q=(n+1)/2; 20 for(i=a[q];k>=0;i++){ 21 while(i==a[q+1])q++; 22 k-=q-(1+n)/2+1; 23 } 24 cout<<i-1; 25 return 0; 26 }
因为我这k=0时还会操作，但是其实不能操作了，所以i++后我输出又要减回去；如果循环内操作完k<0，那说明之前执行i++的操作无效，所以也是i减回去，最后都输出i-1.
0 条评论