codeforces #577(div.2) Maximum Median

原题链接:https://codeforces.com/contest/1201/problem/C

题目大意:给你一组数(奇数个数)和一个数,这个k可以分配给这组数中的某些数,分配完之后,使这组数的中位数越大越好,输出将k分配后能使这组数中位数最大的那个中位数

蛮简单的一道题,做了一个多小时,看见大佬们几分钟A掉,而我却不停地WA。。。。

我的做法很容易想到,先排一次序,从中间那个数开始,配合给的k,看能不能使中位数变成下一位

注意下细节

代码:

#include <bits/stdc++.h>
using namespace std;
long long a[300000];
int main()
{
    long long n,k;
    scanf("%lld %lld",&n,&k);
    for(int i=0;i<n;i++)
    {scanf("%lld",&a[i]);}
    sort(a,a+n);
    if(n==1)
    {printf("%lld\n",a[0]+k);}
    else{
    long long op=n/2;
    //int flag=0;
    long long cnt=1;
    int i;
    long long lpl=a[op];
    for(i=op;i<n-1;i++)
    {
        if(k>=((a[i+1]-a[i])*cnt))
        {
            k-=(a[i+1]-a[i])*cnt;
            //a[i]=a[i+1];
            lpl=a[i+1];
            cnt++;
        }
        else
        {
            lpl+=k/(i-op+1);
            k=0;
            break;
        }
    }
    lpl+=k/(op+1);
    printf("%lld\n",lpl);
    }
    return 0;
}

 

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注