题解：CF613B Skills

Ciallo_Error · 2025-11-26 20:00:33 · 题解

CF613B Skills

题目大意：

定义 sum 为等级为 A 的技能数量，level 为所有技能里面的最低等级。

给出了 n 个技能等级，和 m 次让技能等级升 1 的加点，限制满级为 A。以及系数 cf 和 cm。

我们需要求出 m 次加点之后， sum \times cf + level \times cm 的最大值。

做法

暴力枚举 + 二分套二分

我们可以发现只有最低等级和最大等级 A 的技能会对最后的答案产生贡献。所以我们可以暴力枚举其中一个， 那么另一个可以通过剩下的加点次数求出。

下方只讲枚举 A 数量的做法。

• 因为考虑的是等级的大小，所以我们先将 a 数组从小到大排序。

  我们先预处理一个前缀和数组，pre_i 记录前面所有的技能都变成 a_i 时所需的加点数（后面会用到）。

• 我们从第 n 个数到第 1 个数枚举。

• 然后我们如何求出可以满足的最低等级呢？从第 0 开始枚举显然时间复杂度太劣，考虑优化。

  因为升的等级越高所需的加点越多，这是一个单增的函数，所以我们可以二分查找满足条件的最大等级。

• 我们再继续考虑二分具体如何实现。

  二分上下界为给定的等级限制 l = 0,r = A。

  我们需要在该等级下，找到所有小于等于该等级的数，再进行所需加点数量的判断。这又如何处理？

  这就是很板的二分了，因为我们的 a 数组已经是有序的，所以我们直接在数组上进行二分查找第一个不大于该等级的数。

  根据我们预处理的前缀和数组，可以快速求出该等级所需要的加点数，与 m 进行判断就好了。

• 我们在枚举过程中选取其中的最大值并记录 A 的数量和 level 的大小就行了。

时间复杂度 O(n\log^2n)，比较卡，但可以通过此题。

代码

这个做法其实比较暴力了，但非常好想，代码实现上细节较多。

代码比较冗余，请读者自行参考。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 10;
struct Node{
    int sum;
    int id;
}a[N];
int ta[N];
int pre[N];

int n, tn;
int A;
int cf, cm;
int m;
int tot;
int ans;
int ansl, ansa;

bool chk(int x, int sum){
    if (a[x].sum < sum) return true;
    else                return false;
}

bool check(int x){

    int l = 1, r = tn;

    while(l < r){
        int mid = (l + r) >> 1;
        if (chk(mid, x)) l = mid + 1;
        else             r = mid;
    }

    l -= 1;

    if (pre[l] + (x - a[l].sum) * l + tot <= m) return true;
    else                                        return false;
}

void init(){
    for (int i = 1; i <= n; i++){
        pre[i] = pre[i - 1];
        pre[i] += (i - 1) * (a[i].sum - a[i - 1].sum);
    }

    return;
}

bool cmp(Node x, Node y){
    return x.sum < y.sum;
}

signed main(){
    scanf("%lld", &n);
    scanf("%lld", &A);
    scanf("%lld%lld", &cf, &cm);
    scanf("%lld", &m);

    for (int i = 1; i <= n; i++){
        scanf("%lld", &a[i].sum);
        a[i].id = i;
    }

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

    n++;
    a[n].sum = A;

    ansa = n;

    init();

    for (int i = n; i >= 1; i--){
        tot += A - a[i].sum;

        if (tot > m) break;

        tn = i;

        int l = 0, r = A;
        while(l < r){ 
            int mid = (l + r + 1) >> 1;
            if (check(mid)) l = mid;
            else            r = mid - 1;
        }

        if (ans < (n - i) * cf + l * cm){
            ans = (n - i) * cf + l * cm;
            ansl = l;
            ansa = i;
        }
    }   

    for (int i = 1; i < n; i++){
        if (a[i].sum < ansl) a[i].sum = ansl;
    }

    for (int i = ansa; i < n; i++){
        a[i].sum = A;
    }

    for (int i = 1; i < n; i++){
        ta[a[i].id] = a[i].sum;
    }

    printf("%lld\n", ans);
    for (int i = 1; i < n; i++){
        printf("%lld ", ta[i]);
    }

    return 0;
}