D1. Magic Powder - 1 - 题解

比赛与标签

比赛: Codeforces Round 350 (Div. 2) 标签: binary search, brute force, implementation 难度: *1400

题目大意喵~

早上好呀，各位Master！今天我们要帮助可爱的 Apollinaria 烤小饼干哦~ ฅ'ω'ฅ

事情是这样的：要烤制一块小饼干，需要 n 种不同的配料。对于第 i 种配料，我们每次需要 a[i] 克。现在我们手里有 b[i] 克第 i 种配料，同时还有 k 克万能的魔法粉末！每一克魔法粉末都可以变成任意一种配料 1 克。

我们的任务就是，计算出利用现有的配料和魔法粉末，最多能烤出多少块小饼干呢？

输入:

第一行是两个整数 n 和 k，代表配料种类数和魔法粉末的克数。
第二行是 n 个整数 a[i]，代表每块饼干需要第 i 种配料的克数。
第三行是 n 个整数 b[i]，代表我们现在拥有第 i 种配料的克数。

输出:

一个整数，表示能烤出的最大饼干数量。

解题思路，来分析一下吧！

喵~ 看到“最大化某个值”这种问题，是不是感觉有点头大呀？别担心，让本猫娘来给你理一理思路！

首先，我们来思考一个简单的问题：如果我们想烤 x 块饼干，我们能不能做到呢？

对于每一种配料 i：

我们总共需要 a[i] * x 克。
我们手头有 b[i] 克。
如果 a[i] * x > b[i]，说明我们自己的配料不够啦，需要用魔法粉末来补充。缺口就是 a[i] * x - b[i] 克。
如果 a[i] * x <= b[i]，那太棒了，这种配料是足够的，不需要魔法粉末帮忙！

把所有配料的缺口加起来，就是我们为了烤 x 块饼干，总共需要消耗的魔法粉末数量。如果这个数量不超过我们拥有的 k 克，那就说明烤 x 块饼干是可行的！

现在，我们来观察一个非常有趣的性质，喵~

如果我们能烤 x 块饼干，那我们肯定也能烤 x-1 块饼干，对吧？因为烤更少的饼干，需要的配料只会更少嘛。
反过来，如果我们连 x 块饼干都烤不出来（配料和魔法粉末都不够），那想烤 x+1 块就更不可能了。

这种“行”与“不行”的分界线非常清晰，并且具有单调性！就像一条线，左边都是“可以烤”，右边都是“烤不了”。

[可以, 可以, 可以, ..., 可以, 不可以, 不可以, ...]

对于这种具有单调性的问题，我们就可以愉快地使用二分答案啦！我们不去一块一块地尝试，而是直接在“饼干数量”这个数轴上进行二分查找，找到那个“可以”与“不可以”的临界点，这个临界点就是我们能烤的最大饼干数！

二分步骤:

确定范围: 饼干数量最少是 0，最多是多少呢？我们可以估算一个比较大的上界。比如，就算所有魔法粉末都用来补充一种配料，最多也就 max(b_i) + k 这么多。在D1的限制下，1000 + 1000 = 2000 已经足够了，设一个稍大一点的数比如 2002 作为上界 high，下界 low 为 0。
编写 check 函数: 这个函数就是我们上面分析的 can_bake(x)，它判断烤 x 块饼干是否可行。
循环二分:
- 取中间值 mid = low + (high - low) / 2。
- 调用 can_bake(mid)：
  - 如果返回 true (可以烤 mid 块)，说明答案可能就是 mid，或者我们还能烤更多！所以我们把 mid 存下来作为备选答案，然后去右半边区间继续找，即 low = mid + 1。
  - 如果返回 false (烤不了 mid 块)，说明 mid 太大了，我们需要减少饼干数量。所以我们去左半边区间找，即 high = mid - 1。
结束: 当 low > high 时，循环结束，我们找到的最后一个可行的 mid 就是最终答案啦！

这样一来，问题就迎刃而解了呢！是不是很巧妙呀？

代码实现喵~

cpp

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

// 为了方便，在竞赛代码中把这些变量设为全局的~
// 在大项目中，最好还是通过参数传递哦。
int n;
long long k;
std::vector<int> a;
std::vector<int> b;

// 这就是我们的 check 函数，判断是否能烤 num_cookies 块饼干，的说！
// 它会计算总共需要多少魔法粉末，然后看看我们够不够用。
// 这个函数是单调的：如果能烤 x 块，那肯定也能烤 x-1 块。
// 正是这个性质，让我们能对答案进行二分查找呐。
bool can_bake(long long num_cookies) {
    long long magic_powder_needed = 0;
    for (int i = 0; i < n; ++i) {
        // 计算第 i 种配料总共需要多少克。
        // 用 long long 防止潜在的溢出，虽然在D1的限制下，这里用 int 也够。
        long long required_grams = (long long)a[i] * num_cookies;

        // 如果我们现有的配料不够，就需要动用魔法粉末啦！
        if (required_grams > b[i]) {
            magic_powder_needed += required_grams - b[i];
        }

        // 一个小小的优化：如果需要的魔法粉末已经超过了我们拥有的，
        // 就没必要再算下去了，肯定做不了这么多饼干。
        if (magic_powder_needed > k) {
            return false;
        }
    }

    // 如果所有配料都满足了，并且魔法粉末也没超支，那就说明是可行的！
    return true;
}

int main() {
    // 快速 I/O，让程序跑得更快一点~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    std::cin >> n >> k;
    a.resize(n);
    b.resize(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }
    for (int i = 0; i < n; ++i) {
        std::cin >> b[i];
    }

    // 对饼干的最大数量进行二分查找！
    long long low = 0;
    // 对于D1的限制，这是一个安全的上界。
    // 就算所有魔法粉末都只给一种配料，最多也就 max(b_i) + k。
    // 1000 + 1000 = 2000，我们用一个稍微大一点的值 2002，很稳妥~
    long long high = 2002;
    long long ans = 0;

    while (low <= high) {
        long long mid = low + (high - low) / 2;
        if (can_bake(mid)) {
            // 如果能烤 mid 块，这可能就是答案了！
            // 但我们更贪心，想试试能不能烤更多，所以往右边找~
            ans = mid;
            low = mid + 1;
        } else {
            // 如果烤不了 mid 块，说明 mid 太大了，我们必须减少数量。
            high = mid - 1;
        }
    }

    std::cout << ans << std::endl;

    return 0;
}

复杂度分析的说

时间复杂度: O(N * log(R)) 的说。这里的 R 是我们二分查找的范围上界（大约是2000）。二分查找本身需要 log(R) 次迭代。在每次迭代中，我们的 can_bake 函数都需要遍历 n 种配料来计算所需的魔法粉末，这是一个 O(N) 的操作。所以总的时间复杂度就是 O(N * log(R)) 啦！
空间复杂度: O(N) 的说。我们主要使用了两个 vector a 和 b 来存储输入的配料信息，它们的大小都是 n。所以空间复杂度是 O(N)。

知识点与总结

这道题是“二分答案”的一个非常经典的入门题呢，Master 学会了吗？

核心思想：答案的单调性 当你遇到求解“最大值最小”或者“最小值最大”这类问题时，一定要想想问题的答案是否具有单调性。如果“当 x 满足条件时，所有小于 x 的值也都满足条件”，或者类似的性质成立，那么二分答案就是你的不二之选！
二分答案模板
- 定义 check(x) 函数: 这是二分的核心，用来判断一个候选答案 x 是否可行。
- 确定二分范围 [low, high]: low 通常是问题可能的最小值，high 是一个足够大的、安全的上界。
- 套用循环: 记住 ans = mid; low = mid + 1; 和 high = mid - 1; 的更新逻辑，就能找到那个最棒的临界点啦。
注意数据范围 在计算 a[i] * num_cookies 时，结果可能会超过 int 的范围，所以使用 long long 是一个非常好的习惯，可以避免不必要的溢出错误哦！

希望这篇题解能帮到你！继续加油，算法的世界还有更多有趣的东西等着我们去探索呢，喵~ (ฅ^•ﻌ•^ฅ)

D1. Magic Powder - 1 - 题解 ​

比赛与标签 ​

题目大意喵~ ​

解题思路，来分析一下吧！ ​

代码实现喵~ ​

复杂度分析的说 ​

知识点与总结 ​