CodeForces 614D Skills

排序+枚举+二分

最大的那些变成A，小的那部分提高最小值

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

const int maxn=+;

int n;

long long A,cf,cm,m;

struct X

{

    long long a;

    long long ans;

    int id;

} s[maxn];

long long sum[maxn];

bool cmp1(const X&a,const X&b)

{

    return a.a<b.a;

}

bool cmp2(const X&a,const X&b)

{

    return a.id<b.id;

}

int main()

{

    scanf("%d%lld%lld%lld%lld",&n,&A,&cf,&cm,&m);

    for(int i=; i<=n; i++)

    {

        scanf("%lld",&s[i].a);

        s[i].id=i;

        s[i].ans=s[i].a;

    }

    sort(s+,s++n,cmp1);

    memset(sum,,sizeof sum);

    for(int i=; i<=n; i++) sum[i]=sum[i-]+s[i].a;

    int ansPos1=,ansPos2=;

    long long Max=-;

    long long ave=;

    for(int i=; i<=n; i++) //最后i个都变成A

    {

        long long cost=A*i-(sum[n]-sum[n-i]);//最后i个都变成A需要的费用

        if(cost>m) break;// 如果费用超过了m，则结束

        cost=m-cost;//剩余的费用

        int left=,right=n-i;//二分查找的范围

        int pos=;

        while(left<=right)

        {

            int mid=(left+right)/;

            if(mid*s[mid].a-sum[mid]<=cost)

            {

                pos=mid;

                left=mid+;

            }

            else right=mid-;

        }

        long long q;

        if(pos!=) q=min(A,(cost-pos*s[pos].a+sum[pos])/pos+s[pos].a);

        else q=A;

        if(q*cm+i*cf>Max)

        {

            Max=q*cm+i*cf;

            ansPos1=pos;

            ansPos2=i;

            ave=q;

        }

    }

    for(int i=n;i>=n-ansPos2+;i--) s[i].ans=A;

    for(int i=;i<=ansPos1;i++) s[i].ans=ave;

    printf("%lld\n",Max);

    sort(s+,s+n+,cmp2);

    for(int i=;i<=n;i++)

    {

        printf("%lld",s[i].ans);

        if(i<n) printf(" ");

        else printf("\n");

    }

    return ;

}