E. Exchange - 题解

比赛与标签

比赛: 2022-2023 ICPC, NERC, Southern and Volga Russian Regional Contest (Online Mirror, ICPC Rules, Preferably Teams) 标签: brute force, math 难度: *1000

喵喵，题目在说什么呀？

主人你好呀~ 这道题是说，我们在一个游戏里，想要买一把价值 n 个银币的武器，但是我们一开始身无分文，呜~

不过呢，我们有两个办法搞到钱：

1. 做任务: 每完成一个任务，就能得到 1 个金币。
2. 交易: 我们可以用 1 个金币换 a 个银币（卖出），也可以用 b 个银币换 1 个金币（买入）。

现在的问题就是，为了凑够至少 n 个银币，我们最少需要完成多少个任务呢？

聪明的猫娘是如何思考的捏？

这道题的关键，就在于那个交易系统啦！我们来分析一下卖出金币的价格 a 和买入金币的价格 b 之间的关系，事情就会变得非常简单喵~

我们可以分成两种情况来讨论呐：

情况一：卖金币比买金币赚得多 (a > b)

当 a > b 的时候，一个神奇的事情发生了！我们可以利用差价来“凭空”赚钱！

想象一下这个流程：

1. 我们先努力做 1 个 任务，得到 1 个 金币作为我们的“启动资金”。
2. 我们把这个金币卖掉，换来 a 个银币。
3. 然后，我们再花 b 个银币把这个金币买回来。

一卖一买之后，我们手上还是有 1 个金币，但是银币却多了 a - b 个！因为 a > b，所以 a - b 是一个正数，我们净赚了银币！

既然可以这样无限循环地赚钱，那么理论上只要我们有 1 个金币，就能刷出无限多的银币。所以，我们只需要完成 1 个任务来获得这最初的 1 个金币就足够啦！

情况二：卖金币不划算 (a <= b)

当 a <= b 的时候，上面那个赚钱的法子就行不通了。如果我们卖掉金币再买回来，银币要么不变，要么还会亏掉，呜呜...

在这种情况下，交易系统对我们来说就没什么“骚操作”空间了。最划算的办法就是老老实实地做任务，然后把所有赚来的金币都直接卖成银币。

假设我们完成了 k 个任务，那么我们就会有 k 个金币。把它们全部卖掉，就能得到 k * a 个银币。 我们的目标是让银币数量至少为 n，也就是： k * a >= n

为了让 k 最小，我们解这个不等式得到 k >= n / a。 因为任务数量 k 必须是整数，所以 k 应该取 n / a 的上取整（ceiling）。在编程里，计算 ceil(n / a) 有一个很方便的整数运算技巧，就是 (n + a - 1) / a 啦！

所以，在这种情况下，我们最少需要完成 (n + a - 1) / a 个任务。

代码时间到！喵~

分析清楚之后，代码就非常简单啦！只需要一个 if-else 判断一下就可以的说~

#include <iostream>
using namespace std;

int main() {
    // 优化一下输入输出，让程序跑得更快喵~
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t; // 读取测试用例的数量
    while (t--) {
        int n, a, b;
        cin >> n >> a >> b;

        // 这是第一种情况：卖金币的价格(a) > 买金币的价格(b)
        // 存在套利空间！
        if (a > b) {
            // 只需要完成1个任务，拿到启动资金（1个金币），
            // 就能通过反复买卖无限刷钱啦~
            cout << "1\n";
        } else {
            // 这是第二种情况：交易不划算或者刚好不亏不赚 (a <= b)
            // 只能老老实实做任务，然后把金币一次性换成银币了喵。
            // 我们需要 n 个银币，每个任务最终能换来 a 个银币，
            // 所以一共需要 ceil(n/a) 个任务。
            // 用整型除法的小技巧就是 (n + a - 1) / a 啦！
            cout << (n + a - 1) / a << '\n';
        }
    }
    return 0;
}

跑得快不快呀？

• 时间复杂度: O(1) 的说。对于每一个测试用例，我们都只进行了一次比较和一次除法运算，这是常数时间的操作，超级快的！
• 空间复杂度: O(1) 的说。我们只需要存储 n, a, b 这几个变量，没有使用额外的空间，非常节省内存呐。

猫娘的小课堂时间~

这道题虽然标签里有 brute force，但其实核心是一个简单的 math 问题哦！

最重要的就是要学会分类讨论！通过分析 a 和 b 的大小关系，我们就能发现两种完全不同的最优策略。

• 当 a > b 时，存在套利机会，问题变得异常简单。
• 当 a <= b 时，回归到了一个简单的向上取整除法问题。

另外，ceil(x / y) 在整数运算中写作 (x + y - 1) / y 是一个非常常用的小技巧，主人一定要记住哦！

希望我的讲解对你有帮助喵~！以后有任何问题，随时都可以来找我！加油哦！(ฅ'ω'ฅ)