题解归档 - cf613B

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf613B
• 本地来源：problems/cf613B/idea.md
• 题目链接：https://codeforces.com/contest/613/problem/B
• 原始标题：cf613B Skills

思路

cf613B Skills

题意

有 (n) 个技能，第 (i) 个等级 (a_i\in[0,A])。Force = (c_f\cdot(\#{a_i=A}) + c_m\cdot\min_i a_i)。最多花 (m) 金币，每次给某技能 +1（不超过 (A)），最大化 Force 并输出一种方案。

做法

排序后枚举「满级」技能个数 cnt（取排序后最大的 cnt 个升到 (A)）。

• 满级代价：(\sum_{i=n-cnt+1}^{n}(A-a_i))，剩余 left = m - cost。
• 若 cnt=n：Force = cnt*cf + A*cm。

• 否则对前 rem=n-cnt 个技能，用 left 尽量抬高最小值 mn：

  • 按升序分段：先把前 1 个抬到 (a_2)，再把前 2 个抬到 (a_3)，…，每段需 (next-mn)*(i+1) 金币；
  • 金币不够时 mn += left/(i+1) 后停止。

取 Force 最大的 cnt，前 rem 个输出 mn，后 cnt 个输出 A，按原下标还原。

复杂度

(O(n^2)) 枚举（(n\le 10^5) 实际可行，因内层均摊）；可优化为 (O(n\log n)) 但常数足够。

样例

1 3 1 + (m=5)：最优满级 1 个（原 3→5，耗 2），剩 3 把另两个 1→2，Force (=10+2=12)。

代码

来源：problems/cf613B/solution.cpp

/* Author: likely
 * Time: 2026-06-08 04:08:40
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,A,cf,cm,m,i,j,cnt,rem,cost,left,cur,ans,bestcnt,savemn,le,ri,mi,zc;
ll out[100005],pre[100005];
pair<ll,ll>p[100005];
bool cmp(pair<ll,ll>x,pair<ll,ll>y){
    return x.first<y.first;
}
ll cal(ll rem,ll h){
    ll i=lower_bound(p,p+rem,make_pair(h,(ll)-1))-p;
    return i*h-pre[i];
}
int main(){
    cin>>n>>A>>cf>>cm>>m;
    for(i=0;i<n;i++){
        cin>>p[i].first;
        p[i].second=i;
    }
    sort(p,p+n,cmp);
    for(i=0;i<n;i++) pre[i+1]=pre[i]+p[i].first;
    ans=-1;
    for(cnt=0;cnt<=n;cnt++){
        cost=cnt*A-(pre[n]-pre[n-cnt]);
        if(cost>m) continue;
        left=m-cost;
        cur=cnt*cf;
        if(cnt==n){
            cur+=A*cm;
            if(cur>ans){
                ans=cur;
                bestcnt=cnt;
                savemn=A;
            }
            continue;
        }
        rem=n-cnt;
        le=p[0].first;
        ri=A;
        mi=le;
        while(le<=ri){
            zc=(le+ri)>>1;
            if(cal(rem,zc)<=left){
                mi=zc;
                le=zc+1;
            }else ri=zc-1;
        }
        cur+=mi*cm;
        if(cur>ans){
            ans=cur;
            bestcnt=cnt;
            savemn=mi;
        }
    }
    for(i=0;i<n;i++) out[i]=savemn;
    for(i=n-bestcnt;i<n;i++) out[p[i].second]=A;
    cout<<ans<<endl;
    for(i=0;i<n;i++){
        if(i) cout<<" ";
        cout<<out[i];
    }
    cout<<endl;
    return 0;
}