Codeforces Round #577 (Div. 2) C. Maximum Median (模拟,中位数)

题意:给你一个长度为奇数\(n\)的序列.你可以对任意元素加上\(k\)次\(1\),求操作后的中位数最大.
题解:先对序列进行排序,然后对中位数相加,如果中位数和后面的元素相等,就对后面所有和当前中位数相等的元素++,然后再对中位数++,不断往复这个过程就好了,具体看代码.

代码:

int n;

ll k;

ll a[N];

ll cnt[N];

int main() {

    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

    cin>>n>>k;

    for(int i=1;i<=n;++i) cin>>a[i];

    sort(a+1,a+1+n);

    int mid=(n+1)/2;

    for(int i=mid+1;i<=n;++i) cnt[i]=a[i]-a[i-1];

    ll ans=a[mid];

    for(int i=mid+1;i<=n;++i){

        ll id=i-mid;

        ll cur=k/id;

        if(cur==0) break;

        k-=min(cnt[i]*id,cur*id);

        ans+=min(cnt[i],cur);

    }

    if(k){

        ll cur=k/(n/2+1);

        ans+=cur;

    }

    cout<<ans<<endl;

    return 0;

}

巴特西

Codeforces Round #577 (Div. 2) C. Maximum Median (模拟,中位数)

最新文章

热门文章