F. Magic Will Save the World - 题解

比赛与标签

比赛: Codeforces Round 894 (Div. 3) 标签: binary search, bitmasks, brute force, dp 难度: *1800

题目大意喵~

有一位名叫 Vika 的魔法少女需要打败 n 只怪物来拯救世界，喵~。 Vika 每秒可以产生 w 点水系法力和 f 点火系法力。要打败第 i 只强度为 s_i 的怪物，她需要消耗 s_i 点水系法力或者 s_i 点火系法力。

Vika 可以瞬间施法，只要法力足够，一秒内可以打败任意数量的怪物。她想知道，打败所有怪物最少需要多少秒呢？

简单来说，就是：

• 输入: 每秒能产生的水系法力 w 和火系法力 f，n 只怪物的强度 s_1, s_2, ..., s_n。
• 输出: 打败所有怪物所需的最短整数时间（秒）。

解题思路大揭秘！

这道题要求我们找到一个“最小时间”，一看到这种“求最小的XX”或者“求最大的XX”的题，嗅觉敏锐的猫娘我呀，第一反应就是——二分答案！呐，是不是很有道理？

我们可以二分我们最终需要的时间 t。如果时间 t 秒是足够的，那么任何比 t 更长的时间 t' (t' > t) 肯定也足够，因为法力只会更多嘛。这种单调性正是使用二分答案的完美前提！

那么，二分的核心就在于 check(t) 函数：给定 t 秒，我们能打败所有怪物吗？

在 t 秒内，Vika 总共能获得：

• total_water_mana = w * t 点水系法力
• total_fire_mana = f * t 点火系法力

现在，我们需要决定每只怪物是用火系法术还是水系法术解决。假设我们用水系法术解决的怪物集合，其总强度为 cost_w；用火系法术解决的怪物集合，其总强度为 cost_f。 为了打败所有怪物，必须满足：

1. cost_w + cost_f = total_strength (所有怪物强度之和)
2. cost_w <= total_water_mana
3. cost_f <= total_fire_mana

把第一个式子代入第三个，我们得到 total_strength - cost_w <= total_fire_mana。 整理一下，就变成 cost_w >= total_strength - total_fire_mana。

所以，check(t) 函数就转化成了一个新的问题：

我们能否从所有怪物强度 s_i 中，选出一个子集，使得这个子集的强度之和 cost_w 满足 total_strength - f * t <= cost_w <= w * t？

喵~ 这不就是经典的子集和问题嘛！我们可以用动态规划（DP）来解决。这个问题和 0/1 背包问题非常像哦！

我们可以预处理出所有可能的子集和。设 dp[j] 为一个布尔值，表示是否存在一个怪物子集，其强度总和恰好为 j。

• 初始化 dp[0] = true（一个怪物都不选，总和为0，这是可行的）。
• 对于每只怪物的强度 s_i，我们来更新 dp 数组： for (j = total_strength; j >= s_i; j--)dp[j] = dp[j] or dp[j - s_i] （倒序循环是为了保证每个物品只被用一次，是 0/1 背包的经典写法哦！）

这个 DP 计算出所有可能的 cost_w。做完 DP 之后，对于二分中的每一个 t，我们都要去检查 [total_strength - f * t, w * t] 这个区间内，是否存在一个 j 使得 dp[j] 为 true。

如果每次都遍历一遍这个区间，效率太低啦。聪明的猫娘想到了一个优化：前缀和！ 我们可以再预处理一个 prefix 数组，prefix[k] 表示 dp[0...k] 中有多少个 true。这样，要查询一个区间 [L, R] 内是否有 true，只需要判断 prefix[R] - prefix[L-1] 是否大于 0 就行了，这可是 O(1) 的查询哦！

所以，最终的算法流程就是：

1. 计算所有怪物的总强度 S。
2. 用 0/1 背包 DP 思想计算出所有可能的子集和，填充 dp 数组。
3. 基于 dp 数组计算前缀和数组 prefix。
4. 二分答案 t，在 check(t) 函数中利用 prefix 数组进行 O(1) 判断。

这样一来，问题就迎刃而解啦！

代码实现喵~

#include <iostream>
#include <vector>
#include <numeric> // 虽然代码里没用，但求和可以用 std::accumulate
#include <algorithm>

using namespace std;

int main() {
    // 提高cin/cout效率，对付大数据量的输入输出很有用哦！
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t_cases;
    cin >> t_cases;
    while (t_cases--) {
        long long w, f;
        int n;
        cin >> w >> f;
        cin >> n;
        vector<long long> s(n);
        long long total = 0;
        for (int i = 0; i < n; i++) {
            cin >> s[i];
            total += s[i];
        }

        int total_int = total;
        // dp[j] 表示是否能凑出强度和为 j 的怪物子集
        vector<bool> dp(total_int + 1, false);
        dp[0] = true; // 不选任何怪物，强度和为0，是可行的

        // 0/1背包DP，预处理所有可能的法力消耗组合
        for (int i = 0; i < n; i++) {
            int val = s[i];
            // 从大到小遍历，防止一个怪物被重复计算
            for (int j = total_int; j >= val; j--) {
                if (dp[j - val]) {
                    dp[j] = true;
                }
            }
        }

        // 预处理前缀和，方便O(1)查询区间内是否存在可行的法力分配方案
        // prefix[i] 表示 dp[0...i] 中有多少个 true
        vector<int> prefix(total_int + 1, 0);
        prefix[0] = dp[0] ? 1 : 0;
        for (int i = 1; i <= total_int; i++) {
            prefix[i] = prefix[i - 1] + (dp[i] ? 1 : 0);
        }

        // 二分答案，寻找最小的耗时 t
        // low_t 是下界，high_t 是一个足够大的上界
        long long low_t = 0, high_t = 2e9; // 一个比较宽松的上界

        long long ans = high_t;

        while (low_t <= high_t) {
            long long mid = low_t + (high_t - low_t) / 2;
            if (mid == 0 && total > 0) { // 时间为0，但有怪要打，肯定不行
                 low_t = mid + 1;
                 continue;
            }
            // 在 mid 秒内能获得的总法力
            long long water_mana = w * mid;
            long long fire_mana = f * mid;

            // 我们需要找到一个用水系法术的成本 cost_w, 满足:
            // cost_w <= water_mana  且  total - cost_w <= fire_mana
            // 变形后得到: total - fire_mana <= cost_w <= water_mana
            long long L_bound = total - fire_mana;
            long long R_bound = water_mana;
            
            // 确保查询的区间是合法的
            long long L_interval = max(0LL, L_bound);
            long long R_interval = min((long long)total_int, R_bound);
            
            bool valid = false;
            if (L_interval <= R_interval) {
                // 用前缀和O(1)检查区间 [L_interval, R_interval] 内是否存在一个dp值为true的下标
                int prev_count = (L_interval > 0) ? prefix[L_interval - 1] : 0;
                if (prefix[R_interval] - prev_count > 0) {
                    valid = true;
                }
            }

            if (valid) {
                // 如果mid时间可行，我们尝试更小的时间
                ans = mid;
                high_t = mid - 1;
            } else {
                // 如果不行，我们需要更多时间
                low_t = mid + 1;
            }
        }

        cout << ans << endl;
    }
    return 0;
}

复杂度分析的说

• 时间复杂度: O(N * S + log(T_max)) 的说。

  • S 是所有怪物的总强度 (total)，N 是怪物数量。
  • O(N * S) 来自于预处理的 DP 部分。这是整个算法的瓶颈。
  • log(T_max) 来自于二分答案，其中 T_max 是时间的上界。每次 check 函数因为有前缀和的帮助，是 O(1) 的。
  • 因为题目保证所有测试用例的 N 总和不超过 100，S 最大约为 100 * 10000 = 10^6，所以这个复杂度是完全可以接受的！

• 空间复杂度: O(S) 的说。

  • 主要空间开销来自于 dp 数组和 prefix 数组，它们的大小都和总强度 S 相关。

知识点与总结喵~

这道题真是一道非常棒的组合拳练习题，考察了多种算法思想的结合，我们来总结一下吧：

1. 二分答案: 解决“求最小/最大值”问题的强大武器。当你发现问题的答案具有单调性时，就应该立刻想到它！
2. 0/1 背包 DP: 它是解决子集和问题的经典方法。将 check 函数的核心转化为一个背包问题是解题的关键一步。
3. 前缀和优化: 这是加速查询的常用技巧。将 O(区间长度) 的查询优化到 O(1)，使得二分答案的整体复杂度大大降低。

所以，解题的思路就是：用二分答案搭起整体框架，用 DP 解决其中的子问题，再用前缀和优化子问题的查询效率。这个模式在很多难题中都会出现，大家一定要掌握哦！

希望这篇题解能帮助到你，如果还有不明白的地方，随时可以来问猫娘我哦！我们下次再见，喵~！