思路

目标:将和中位数相等的数并且排在中位以及中位的后面的一些数尝试更新为大于中位数的最小数.

只要排过序之后,k足够的情况下不断更新即可,更新的过程中一定是保序的,不需要重复排序.

为了完成目标两步操作,第一步的更新是区间更新,第二步是查询中位数的后继,故区间更新,单点查询,二分,使用树状数组维护差分来做.

代码

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

typedef long long ll;
using namespace std;
const int N = 2e5 + 10;
int a[N];
int b[N];
int n,k;
int tr[N];

int lowbit(int x){
    return x & -x;
}

void add(int x, int c) {
    for (int i = x; i <= n; i += lowbit(i)) tr[i] += c;
}

int sum(int x) {
    int res = 0;
    for (int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}


int main()
{
    scanf("%d%d",&n,&k);
    for(int i = 1; i <= n; ++ i)
        scanf("%d", &a[i]);

    sort(a+1,a+n+1);//n/2+1
    for(int i = 1; i <= n; ++ i){//注意要先排序再建立差分
        b[i] = a[i] - a[i-1];
        add(i,b[i]);
    }

    int n_2 = n / 2 + 1;//中位
    while(k){
        int zhong = sum(n_2);//当前中位数
        int l = 1,r = n ;
        while(l < r){//查中位数后继
            int mid = l + r  >> 1;
            if(sum(mid) <= zhong )l = mid + 1;
            else r = mid;
        }
        int tar;//尝试将一群"中位数"修改为大于中位数的最小数tar
        if(sum(r)!=zhong){//有可能查到大于中位数,中位数后继向前移动一位
            tar = sum(r);
            r --;
        }else{
            tar = -1;//否则说明和中位数相等的数一直延续到最后一个数.
        }
        int len = r - (n_2) + 1;//一群"中位数的个数"

        if(k < len){//k不够len说明不够更新,跳出
            cout<<sum(n_2)<<endl;
            return 0;
        }
        if(tar != -1){//
            int d = tar - zhong;
            if(k > d * len ){//足够更新到tar则更新
                add(n_2,d),add(r+1,-d);
                k -= d * len;
            }else{//否则能更新多少更新多少
                cout<<sum(n_2)+k/len <<endl;
                return 0;
            }
        }else{
            int t = k / len;//不够更新,能更新多少更新多少
            cout<<sum(n_2) + t<<endl;
            return 0;
        }
    }


    return 0;
}