题解：P12370 [蓝桥杯 2022 省 Python B] 技能升级

· · 题解

P12370 [蓝桥杯 2022 省 Python B] 技能升级

题意分析

一共有 N 个可以加攻击力的技能。其中第 i 个技能首次升级可以提升 A_i 点攻击力，以后每次升级增加的点数都会减少 B_i，减到负数就不再减了，总计可以升级 M 次技能，可以任意选择升级的技能和次数。求最大值？

思路

首先贪心，很容易想到每次加最大值是最优解，欸那这不就是单点修改，区间查询吗，直接线段树…等等 M 是多少？既然 M 这么大，模拟显然没法做，只能找一找性质了。

如果我们把每个 A_i 抽象成一条线段的话，就能得到这样一个 A。觉得图糊的别找我，因为我也不知道怎么让上传到图床里的图片清晰一点（逃）。

那么经过操作之后，大概会变成这样。

仔细观察这个图，就能发现操作结束后 \forall A_i 都是小于一个值的，即图中的直线。我们考虑找到这个值（现在你知道标签里为啥有二分了吧）。对这个值二分，计算每个 A_i 的贡献，如果在这条直线右边的线段过多（即超过了 M），就去掉最小值，我是将所有 A_i 的最小值记录在一个数组中，要删直接从小到大删即可。

#include<bits/stdc++.h>
using namespace std;

long long n, m, a[100005], b[100005], c[100005], maxn, l, r, x, tot, ans, cnt, mid;

int main() {
    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i];
        maxn = max(maxn, a[i]);//记录最大值
    }

    l = 0, r = maxn;
    while(l <= r) {
        tot = 0;
        x = (l + r) / 2;
        for(int i = 1; i <= n; i++) {
            if(a[i] >= x) tot += (a[i] - x) / b[i] + 1;
        }
        if(tot >= m) l = x + 1, mid = x;
        else r = x - 1;
    }//二分查找

    tot = 0;

    for(int i = 1; i <= n; i++) {
        if(a[i] >= mid) {
            cnt = (a[i] - mid) / b[i] + 1;
            tot += cnt;
            ans += (a[i] * 2 - (cnt - 1) * b[i]) * cnt / 2;
            a[i] -= (cnt-1) * b[i];
            c[i] = a[i];
        }
    }//贪心加和

    sort(c+1, c+1+n);

    int j = 1;

    for(int i = 1; i <= tot - m; i++) {
        if(j > n) break;
        if(c[j] == 0) {j++, i--; continue;}
        ans -= c[j];
    }//修改

    cout << ans;
    return 0;
}

无耻求赞。