F. Final Boss - 题解

比赛与标签

比赛: Codeforces Round 952 (Div. 4) 标签: binary search, data structures 难度: *1500

喵喵，题目讲了什么呀？

这道题呀，是说我们要去挑战一个有 h 点血量的大魔王，我们手上有 n 种不同的攻击技能。

每个技能 i 都有自己的伤害值 a_i 和冷却时间 c_i。游戏的规则是这样的：

1. 在每一回合，我们可以把所有不在冷却中的技能一次性全部用出去，对魔王造成成吨的伤害！
2. 一个技能如果在第 x 回合使用了，那么它下一次能用就要等到第 x + c_i 回合了。
3. 游戏开始的第一回合，所有技能都是准备就绪的，随时可以发射！
4. 如果某一回合所有技能都在冷却，那我们就只能眼巴巴地看着，跳过这一回合，等待下一回合技能转好，的说。

我们的任务就是，计算出最少需要多少个回合，才能把大魔王的血量打到 0 或者更低呢？

如何打败大魔王喵？—— 思路分析

主人请想一想，如果我们用的回合数越多，对魔王造成的总伤害是不是也肯定会越多（或者至少不会变少）呀？

对啦！这就是一个非常重要的性质，我们称之为单调性。如果 k 个回合能打败魔王，那么 k+1 个回合肯定也能打败它。反过来，如果 k 个回合打不败，那么比 k 少的回合数也肯定打不败。

一看到这种“求最小/最大的xx，使得xxx条件成立”并且具有单调性的问题，我们聪明的猫娘脑海里第一个蹦出来的词就是——二分答案！喵~

我们可以不对具体的回合数一个一个去试，而是在一个很大的回合数范围里进行二分查找。比如，我们猜一个回合数 mid，然后去检查：

“在 mid 个回合内，我们能打败魔王吗？”

这就是我们的 check(mid) 函数的核心任务。如果能，说明真正的答案可能比 mid 更小（或者就是 mid），我们就在 [1, mid] 这个范围里继续找。如果不能，说明 mid 回合不够，我们必须用更多的时间，就在 [mid+1, 很大很大的数] 这个范围里继续找。

那么，关键问题就变成了如何实现 check(k) 函数，也就是如何计算在 k 个回合内能造成的总伤害呢？

对于第 i 个技能，它的冷却时间是 c_i。它会在第 1 回合、第 1 + c_i 回合、第 1 + 2*c_i 回合……被使用。这是一个公差为 c_i 的等差数列！我们要计算的是，在 1 到 k 回合内，这个技能总共能用多少次。

假设它能用 m+1 次，最后一次使用是在 1 + m * c_i 回合。这个回合数必须小于等于 k，所以： 1 + m * c_i <= km * c_i <= k - 1m <= (k - 1) / c_i

因为 m 是整数，所以 m 最大能取到 floor((k - 1) / c_i)。由于次数是从 m=0 开始算的（第1次），所以总共的使用次数就是 m + 1，也就是 (k - 1) / c_i + 1 次（在 C++ 中，整数除法自动向下取整）。

知道了每个技能的使用次数，再乘以各自的伤害 a_i，然后把所有技能造成的伤害加起来，就得到了 k 回合内的总伤害！

总伤害 = Σ ( ( (k - 1) / c_i + 1 ) * a_i ) （对所有 i 从 1 到 n 求和）

一个超级重要的陷阱喵！ 主人你看，回合数 k 可能会非常大（比如 10^10 级别），伤害 a_i 也不小。它们相乘，再和 n 个技能的总和加起来，总伤害可能会超过 long long 的最大值（大约 9 * 10^18）。所以，在计算总伤害时，我们需要用一个更大的数据类型，比如 unsigned __int128，来防止溢出，不然就会得到错误的答案啦！

所以，我们的完整思路就是：

1. 确定一个足够大的二分搜索范围，比如 [1, 4*10^10]。
2. 在范围内进行二分，每次取中间值 mid。
3. 调用 check(mid) 函数，用 unsigned __int128 计算 mid 回合内的总伤害。
4. 如果总伤害大于等于 h，说明 mid 可行，尝试更小的回合数。
5. 如果总伤害小于 h，说明 mid 不可行，需要更多的回合数。
6. 最终找到的最小可行回合数就是答案啦！

代码魔法，变身！喵~

#include <iostream>
#include <vector>
#include <numeric>

// 这个函数用来检查，在 'k' 个回合内能不能打败魔王，喵~
// 因为总伤害是随着回合数 'k' 单调递增的，所以我们可以对 'k' 进行二分查找！
bool check(long long k, long long h, int n, const std::vector<int>& a, const std::vector<int>& c) {
    // 这里我们用 128 位的无符号整数来计算总伤害，防止溢出哦！
    // 因为回合数 'k' 可能非常大 (高达 4e10)，总伤害会超出 64 位整数 (long long) 的范围。
    unsigned __int128 total_damage = 0;
    for (int i = 0; i < n; ++i) {
        // 题目说，如果一个技能在第 'x' 回合用，下一次就要在 'x + c_i' 回合。
        // 这意味着每个技能的使用时机是固定的，不受其他技能影响。
        // 技能 'i' 会在第 1, 1+c_i, 1+2*c_i, ... 回合被使用。
        // 在 'k' 个回合内，技能 'i' 的使用次数就是这个序列中小于等于 'k' 的项数。
        // 这个次数就是 floor((k-1)/c_i) + 1，也就是下面的表达式啦。
        unsigned __int128 num_uses = (unsigned __int128)(k - 1) / c[i] + 1;
        
        // 把这个技能造成的伤害加到总伤害里去。
        // 乘法也是在 128 位下进行的，非常安全！
        total_damage += num_uses * a[i];
        
        // 一个小优化：如果当前总伤害已经超过了魔王的血量，
        // 就没必要继续算了，直接返回 true 就好啦！因为伤害都是正的，只会越来越多。
        if (total_damage >= h) {
            return true;
        }
    }
    
    // 检查完所有技能，看看总伤害够不够。
    return total_damage >= h;
}

void solve() {
    long long h;
    int n;
    std::cin >> h >> n;
    std::vector<int> a(n);
    std::vector<int> c(n);
    for (int i = 0; i < n; ++i) std::cin >> a[i];
    for (int i = 0; i < n; ++i) std::cin >> c[i];
    
    // 二分查找最小需要的回合数。
    long long low = 1;
    // 回合数的上界可以估算一下：最坏情况是血量最多(h_max=2e5), 只有一个攻击力为1的技能(a_1=1), 
    // 并且冷却时间最长(c_1=2e5)。需要的的回合数大约是 h * c = 2e5 * 2e5 = 4e10。
    // 我们用一个稍微大一点的数作为上界，确保万无一失。
    long long high = 40000000001LL; 
    long long ans = high; // 初始化答案为一个很大的值
    
    while (low <= high) {
        long long mid = low + (high - low) / 2; // 这样写可以防止 low+high 溢出
        if (check(mid, h, n, a, c)) {
            // 如果 'mid' 个回合足够了，那它就是一个潜在的答案。
            // 我们试着找找看有没有更少的回合数也能成功，所以缩小右边界。
            ans = mid;
            high = mid - 1;
        } else {
            // 如果 'mid' 个回合还不够，那我们必须花更多的时间，所以扩大左边界。
            low = mid + 1;
        }
    }
    std::cout << ans << "\n";
}

int main() {
    // 加速输入输出，让程序跑得更快，喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    
    return 0;
}

时空魔法的消耗~

• 时间复杂度: O(N * log(K)) 的说。 这里的 N 是技能的数量，K 是我们二分查找范围的上界（大约 4*10^10）。二分查找本身需要 log(K) 次迭代，每次迭代中的 check 函数都需要遍历 N 个技能来计算总伤害。所以总的时间复杂度就是 O(N * log(K)) 啦。

• 空间复杂度: O(N) 的说。 我们主要需要两个数组来存储 n 个技能的伤害值和冷却时间，所以空间开销是线性的，和技能数量成正比。

猫娘的小课堂时间~

这道题真是一个非常经典的“二分答案”模型呢，主人以后遇到类似“求最小/最大的...以满足...”的问题，都可以先往这个方向想一想哦！

核心思想:

• 答案单调性: 发现问题答案具有单调性是解题的第一步。回合数越多，伤害越高，这就是一个完美的单调关系。
• 二分答案: 利用单调性，将求解问题转化为判定问题（check函数），通过二分法高效地锁定答案的范围，最终找到最优解。

编程技巧与注意事项:

• 警惕整数溢出！: 这是算法竞赛中常见的陷阱，喵！当数值范围很大时，一定要检查中间计算结果是否会超出 long long 的表示范围。这道题的 unsigned __int128 就是一个很好的例子。
• 二分边界: check 函数的实现方式决定了二分查找的写法。我们写的 check(k) 是判断 k 回合是否足够，所以当 check(mid) 为真时，ans = mid，然后尝试更小的 high = mid - 1。
• 计算公式: 正确推导出 k 回合内技能的使用次数 (k-1)/c_i + 1 是 check 函数的关键。

总之，这道题考察了我们发现问题本质（单调性）并应用经典算法（二分答案）的能力，还顺便考验了一下我们对数据范围的敏感度。只要掌握了这些，再遇到类似的魔王也不怕啦！加油，主人！喵~