题意（CodeForces 614D）

每个人有\(n(n\le 10^5)\)个技能，技能等级都在\([0,10^9]\)的范围，每个技能有一个当前等级，所有技能的最高等级都为A。一个人的力量被记做以下两项的和：

1. 顶级技能的个数 *cf

2. 最低等级的技能 *cm

每个单位的钱能够提升一级力量。我们希望花尽可能少的钱，使得力量尽可能高。

分析

我二分的功力还是不足，要多努力。这题其实是一个非常明显的暴力：我们枚举提高到A的等级的个数（到不能提升为止），枚举这种情况下，我们能够令把多少人的等级提升到相同的某个等级——这个地方可以用二分解决（先排序）。这样遍历一遍整个等级，就能得到最优的策略，然后输出答案即可。具体的代码细节见注释。

代码

/*

 * Filename: cfr339d2d.cpp

 * Date: 2018-11-07

 */

#include <bits/stdc++.h>

#define INF 0x3f3f3f3f

#define PB emplace_back

#define MP make_pair

#define fi first

#define se second

#define rep(i,a,b) for(repType i=(a); i<=(b); ++i)

#define per(i,a,b) for(repType i=(a); i>=(b); --i)

#define ZERO(x) memset(x, 0, sizeof(x))

#define MS(x,y) memset(x, y, sizeof(x))

#define ALL(x) (x).begin(), (x).end()

#define QUICKIO                  \

    ios::sync_with_stdio(false); \

    cin.tie(0);                  \

    cout.tie(0);

#define DEBUG(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)

using namespace std;

using pi=pair<int,int>;

using repType=int;

using ll=long long;

using ld=long double;

using ull=unsigned long long;

const int MAXN=100005;

struct Skill

{

    int v,o;

    Skill() {}

    Skill(int _v, int _o):v(_v), o(_o) {}

} a[MAXN];

int n;

ll A,cf,cm,m,sum[MAXN];

int solve(int R, ll now) // given present cost, and r which tells 1~r are not A,

{                        // which lowest lv can you reach?

    if(R==0) return A;

    int l=1, r=R;

    while(l<r)

    {

        int mid=(l+r+1)/2;

        ll need=ll(a[mid].v)*mid-sum[mid];  // we need it to make pre n people

        if (need>now) r=mid-1; else l=mid; // reach the lv of the nth.

    }

    ll need=ll(a[l].v)*l-sum[l];

    ll more=(now-need)/l;

    return min(ll(A), a[l].v+more);

}

int

main()

{

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

    rep(i,1,n)

    {

        scanf("%d", &a[i].v);

        a[i].o=i;

    }

    sort(a+1, a+n+1, [](Skill& x, Skill& y) -> bool

                     {

                         return x.v<y.v;

                     });

    a[n+1].v=A;

    rep(i,1,n) sum[i]=sum[i-1]+a[i].v;

    ll ans=-1, cost=0;

    int v,p;

    per(i,n,0)

    {

        cost+=A-a[i+1].v; if(cost>m) break;

        int minv=solve(i,m-cost);

        ll tmp=minv*cm+(n-i)*cf;

        if(tmp>ans)

        {

            ans=tmp;

            p=i;

            v=minv;

        }

    }

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

    per(i,n,p+1) a[i].v=A;

    rep(i,1,p) a[i].v=max(a[i].v, v);

    sort(a+1, a+n+1, [](Skill& x, Skill& y) -> bool

                     {

                         return x.o<y.o;

                     });

    rep(i,1,n)

        printf("%d ", a[i].v);

    printf("\n");

    return 0;

}

巴特西

「日常训练」Skills（Codeforce Round #339 Div.2 D）

题意（CodeForces 614D）

分析

代码

最新文章

热门文章