F. Bomb - 题解

比赛与标签

比赛: Codeforces Round 962 (Div. 3) 标签: binary search, greedy, math 难度: *1900

引爆炸弹前的最后冲刺喵！

主人，你好呀！这道题是说，我们有两个数组 a 和 b，还有 k 次操作机会。每一次操作，我们可以选择一个下标 i，给我们的总分加上当前的 a[i]，然后 a[i] 就会变成 max(0, a[i] - b[i])。我们的任务就是在炸弹爆炸前，也就是在 k 次操作内，拿到尽可能高的分数！

简单来说就是：

输入: 数组长度 n，操作次数 k，数组 a 和 b。
操作: 选 i，得分 a[i]，然后 a[i] -= b[i]（不小于0）。
目标: k 次操作后，总分最大化！

贪心和二分法的奇妙相遇~

喵~ 看到要让总分最大，我们的小脑袋瓜里第一个蹦出来的念头肯定是贪心啦！每次都选当前分数最高的 a[i]，这肯定是最赚的嘛！(๑•̀ㅂ•́)و✧

但是，主人你看，k 的值可以非常非常大（高达 10^9），如果我们一次一次地模拟操作，肯定会超时的说。所以，直接模拟这个贪心策略是行不通的。

这时候就要转变思路啦！既然不能一步步地决定“下一步选哪个”，我们可以换个角度问问题：“我们愿意接受的最低分数是多少？”

假设我们设定一个分数门槛 T，我们只执行那些得分不低于 T 的操作。

如果 T 定的太高，可能所有能做的操作加起来都凑不够 k 次。
如果 T 定的太低，我们能做的操作就很多，肯定超过 k 次了。

发现了嘛？我们能进行的操作次数和我们设置的最低分数门槛 T 之间，存在一种奇妙的 单调关系！门槛 T 越高，能做的操作次数就越少。这种单调性，简直就是为 二分答案 量身定做的喵！

所以，我们的核心思路就是 二分答案，二分我们能接受的 最低操作得分 T_0。这个 T_0 实际上就是我们进行的 k 次操作中，得分最低的那一次的分数。

二分过程是这样哒：

确定二分范围: 分数的最小值可能是 1，最大值可能是 a 数组里的最大值。所以我们的二分范围可以设为 [1, max(a_i) + 1]。
check(T) 函数: 对于一个二分出的门槛 T，我们需要计算出，如果只做得分不低于 T 的操作，总共能做多少次。
- 对于每个 i，只要 a[i] >= T，我们就可以一直操作下去。每次操作后 a[i] 减少 b[i]。那么，对于一个初始的 a[i]，能做多少次得分不低于 T 的操作呢？次数就是 (a[i] - T) / b[i] + 1 次。
- 我们把所有 i 的这个次数加起来，得到总操作数 count。
调整范围:
- 如果 count >= k，说明以 T 为门槛，我们能凑够 k 次操作。这说明真正的最低分 T_0 可能等于 T，甚至可能更高！所以我们尝试提高门槛，low = T + 1。
- 如果 count < k，说明门槛 T 太高了，我们凑不够 k 次操作。必须降低门槛才行，high = T。

通过这个二分过程，我们最终会找到一个临界值 T_0（在代码里是 low - 1）。这个 T_0 就是我们 k 次操作里，价值最低的那一次操作的得分。

找到 T_0 后如何计算总分呢？

我们的 k 次操作可以分成两部分：

所有得分 严格大于 T_0 的操作。我们必须把这些都做了！
剩下的操作次数，全部用来做那些得分 恰好等于 T_0 的操作。

所以，计算总分的步骤如下：

遍历所有 i，计算如果只做得分 > T_0（也就是 ≥ T_0 + 1）的操作，能做多少次（设为 j_i），以及这些操作的总分是多少。
- 对于每个 i，这 j_i 次操作的得分是一个等差数列：a[i], a[i]-b[i], ..., a[i]-(j_i-1)b[i]。
- 求和可以用等差数列求和公式：a[i] * j_i - b[i] * (j_i * (j_i - 1)) / 2。
把所有 i 的这些次数和分数加起来，得到总次数 F_plus 和总分数 S_plus。
我们还剩下 k - F_plus 次操作机会。根据我们二分出的 T_0 的定义，这些剩下的操作，每一次的得分都恰好是 T_0。
所以，最终的总分就是 S_plus + (k - F_plus) * T_0。

还有一个小小的特殊情况喵~ 如果 k 比所有 a[i] 能被操作的总次数还要大，那我们就可以把所有可能的操作都做完。直接对每个 i 计算其所有操作的总和（还是用等差数列求和）然后加起来就好啦！

让代码动起来喵！

cpp

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    // 加速输入输出，让程序跑得更快喵~
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        long long n, k;
        cin >> n >> k;
        vector<long long> a(n);
        vector<long long> b(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        for (int i = 0; i < n; i++) {
            cin >> b[i];
        }

        // x_max[i] 表示第 i 个元素能被操作的总次数
        vector<long long> x_max(n);
        long long P = 0; // P 是所有元素能被操作的总次数之和
        long long max_a = 0; // 找到 a 数组中的最大值，用于二分上界
        for (int i = 0; i < n; i++) {
            max_a = max(max_a, a[i]);
            // (a[i] - 1) / b[i] + 1 是向上取整 a[i]/b[i] 的一种写法，计算总操作次数
            x_max[i] = (a[i] - 1) / b[i] + 1;
            P += x_max[i];
        }

        // 特殊情况：如果 k 比总共能操作的次数还多，就把所有操作都做完
        if (k > P) {
            long long ans = 0;
            for (int i = 0; i < n; i++) {
                // 等差数列求和：a[i] + (a[i]-b[i]) + ...
                // S = n*a1 + n*(n-1)/2*d, 这里 d = -b[i]
                ans += a[i] * x_max[i];
                ans -= b[i] * (x_max[i] * (x_max[i] - 1)) / 2;
            }
            cout << ans << '\n';
        } else {
            // 二分答案，寻找最低得分门槛
            long long low = 1, high = max_a + 1;
            while (low < high) {
                long long mid = low + (high - low) / 2; // 防止溢出
                long long count = 0; // 记录得分不低于 mid 的操作有多少次
                for (int i = 0; i < n; i++) {
                    if (a[i] < mid) continue; // 如果初始值就小于门槛，不可能有得分 >= mid 的操作
                    // 计算得分不低于 mid 的操作次数
                    long long j_i = (a[i] - mid) / b[i] + 1;
                    // j_i 不能超过这个元素本身的最大操作次数
                    if (j_i > x_max[i]) j_i = x_max[i];
                    count += j_i;
                }
                
                if (count < k) { // 操作次数不够，说明门槛 mid 太高了
                    high = mid;
                } else { // 操作次数足够，说明门槛 mid 可能OK，或者可以更高
                    low = mid + 1;
                }
            }
            
            // 循环结束后, low 是第一个使得 count < k 的值
            // 所以我们能接受的最低分数 T0 是 low - 1
            long long T0 = low - 1;
            
            long long F_plus = 0; // 得分 > T0 的操作总次数
            long long S_plus = 0; // 得分 > T0 的操作总得分

            for (int i = 0; i < n; i++) {
                if (a[i] < T0 + 1) continue; // 如果初始值就不大于 T0, 就不可能有得分 > T0 的操作
                // 计算得分严格大于 T0 (即 >= T0+1) 的操作次数
                long long j_i = (a[i] - (T0 + 1)) / b[i] + 1;
                if (j_i > x_max[i]) j_i = x_max[i];
                
                F_plus += j_i;
                // 计算这 j_i 次操作的总分
                S_plus += a[i] * j_i - b[i] * (j_i * (j_i - 1)) / 2;
            }
            
            // 剩下的操作次数，每次得分都是 T0
            long long take_T0 = k - F_plus;
            long long ans = S_plus + T0 * take_T0;
            cout << ans << '\n';
        }
    }
    return 0;
}

跑得快不快呀？

时间复杂度: O(N log A_max) 的说。对于每个测试用例，我们进行一次二分查找。二分的范围是 [1, max(a_i)]，所以二分部分是 log(A_max)。在每次二分 check 的时候，我们需要遍历整个长度为 N 的数组来计算 count。所以总的时间复杂度就是 O(N * log(A_max)) 啦，非常高效！
空间复杂度: O(N) 的说。我们主要用了几个和 n 等大的 vector 来存储 a, b 和 x_max，所以空间开销是线性的。

这次探险的宝藏~

这次解题就像一次寻宝探险，我们收获了满满的知识点呐！

贪心 + 二分 (二分答案): 这是解决最优化问题的一个超级经典的模型！当直接贪心因为步骤太多而超时，并且答案满足单调性时，就可以考虑二分答案。我们把问题从“求最大值/最小值”转换成“判断一个值 X 是否可行”。
数学技巧: 熟练运用等差数列求和公式 S = n*a1 + n*(n-1)/2*d 可以大大简化计算，避免在 check 函数里再写循环，从而保证效率。
边界处理: 像 k 大于总操作次数这样的特殊情况要单独考虑。二分查找的边界 [low, high) 和更新条件 low = mid + 1、high = mid 也要想清楚，才能准确地找到我们想要的那个临界值 T_0 喵。

掌握了二分答案的思想，很多看起来要超时的贪心问题都能迎刃而解啦！主人也要多多练习，变得更强哦！继续加油喵~ ( ´ ▽ ` )ﾉ

F. Bomb - 题解 ​

比赛与标签 ​

引爆炸弹前的最后冲刺喵！ ​

贪心和二分法的奇妙相遇~ ​

让代码动起来喵！ ​

跑得快不快呀？ ​

这次探险的宝藏~ ​