算法

贪心 $O(NlogN)$

这个题N是奇数,mid=(n+1)/2,因为增加mid之前的数明显不划算，所以可以从mid处开始向后推进。
a[mid]->a[mid+1]需要a[mid+1]-a[mid]

当 a[mid] 达到a[mid+1] 时,要想再增大中位数,就需要同时增大a[mid],a[mid+1]
a[mid],a[mid+1]->a[mid+2]需要2*(a[mid+2]-a[mid+1])
同理：
a[mid],a[mid+1]..a[mid+m-1]->a[mid+m]需要m*(a[mid+m]-a[mid+m-1])

最后如果无法到达下一个数且此时k并没有减完,则最后的结果再加上(剩余的k) $\div$ (当前同步提升的数的个数)

C++ 代码

#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int N = 2e5+10;
LL a[N];
int main(){
    int i,j,n;
    LL k;
    cin>>n>>k;
    for(i=1;i<=n;i++){
        cin>>a[i];
    }
    sort(a+1,a+n+1);
    int mid=n/2+1;
    LL co=1,ans=a[mid];//co表示目前要增大中位数需要同时增大的数的个数

    //当a[mid]=a[mid+1]时,此时若还想增大中位数的值,就需要两个同时增大
    for(mid;mid<n;mid++){
        LL t=a[mid+1]-a[mid];
        if(k>=co*t){ //判断是不是可以同时增大co个数
            ans+=t;
            k-=t*co;
            co++;
        }
        else(
            if(co==1)ans+=k,k=0;//一开始k就不足以支撑a[mid]到a[mid+1],k要记得变为0
            break;
        )
    }
    ans+=k/co;//最后再挣扎一波,如果k还剩余,看一下还能不能提升
    cout<<ans<<endl;
    return 0;
}