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

题目描述

小蓝最近正在玩一款 RPG 游戏。他的角色一共有 $N$ 个可以加攻击力的技能。其中第 $i$ 个技能首次升级可以提升 $A_i$ 点攻击力，以后每次升级增加的点数都会减少 $B_i$。$\lceil \frac{A_i}{B_i}\rceil$（上取整）次之后，再升级该技能将不会改变攻击力。

现在小蓝可以总计升级 $M$ 次技能，他可以任意选择升级的技能和次数。请你计算小蓝最多可以提高多少点攻击力？

输入格式

输入第一行包含两个整数 $N$ 和 $M$。

以下 $N$ 行每行包含两个整数 $A_i$ 和 $B_i$。

输出格式

输出一行包含一个整数表示答案。

输入输出样例 #1

输入 #1

3 6
10 5
9 2
8 1

输出 #1

47

说明/提示

评测用例规模与约定

• 对于 $40\%$ 的评测用例, $1\le N,M\le 1000$;
• 对于 $60\%$ 的评测用例, $1\le N\le 10^4$, $1\le M\le 10^7$;
• 对于所有评测用例, $1\le N\le 10^5$, $1\le M\le 2\times 10^9$, $1\le A_i,B_i\le 10^6$。

C++实现

#include <iostream>
#include <algorithm>
using namespace std;
const int MAX_N = 100000;
int N, M, A[MAX_N], B[MAX_N], max_A = 0;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N >> M;
    for (int i = 0; i < N; ++i) {
        cin >> A[i] >> B[i];
        max_A = max(max_A, A[i]);
    }
    int left = 0, right = max_A, best_x = 0;
    while (left <= right) {
        int mid = (left + right) / 2;
        long long total = 0;//攻击总量
        for (int i = 0; i < N; ++i)
            if (A[i] >= mid)
                total += (A[i] - mid) / B[i] + 1;
        if (total >= M) best_x = mid, left = mid + 1;//寻找最优阈值，即越大越好
        else right = mid - 1;
    }
    long long tot = 0, cnt = 0;
    for (int i = 0; i < N; ++i) {
        if (A[i] < best_x) continue;//即攻击力超过阈值才会升级
        int k = (A[i] - best_x) / B[i] + 1;
        cnt += k;
        tot += k * (2LL * A[i] - (k - 1) * B[i]) / 2;
    }
    cout << tot - (cnt > M ? (cnt - M) * best_x : 0);
    return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容