F. Workout plan - 题解

哈喵~！各位热爱算法的伙伴们，大家好呀！我是你们的解题猫娘，最喜欢用爪子挠开算法题的神秘面纱啦！今天我们要征服的这道题，是一个关于健身计划和精打细算的小故事，听起来就很有趣，对吧？让我们一起看看怎么用最少的钱钱，变成健身达人吧！喵~

比赛与标签

比赛: Bubble Cup 12 - Finals [Online Mirror, unrated, Div. 1] 标签: data structures, greedy 难度: *1500

题目大意喵~

简单来说，我们有一个为期 N 天的健身计划，每天的目标是举起 X[i] 克的重量。我们初始的力量是 K。

为了变得更强，我们每天都可以在健身房买一瓶神奇的增肌饮料，价格是 C[i]。每喝一瓶，我们的力量就能永久增加 A 克，而且效果是立竿见影的！

我们的任务就是，在保证每天都能完成举重目标的前提下，花最少的钱买饮料。如果无论如何都无法完成计划，就要告诉Alan这个坏消息，输出 -1 呐。

输入:

N 和 K: 计划天数和初始力量。
X[i]: 第 i 天要举起的重量。
A: 每瓶饮料增加的力量值。
C[i]: 第 i 天饮料的价格。

输出:

完成计划的最小总花费。如果不可能，就输出 -1。

贪心思路大揭秘！

这道题的核心，其实是一个非常经典的贪心思想，喵~ 我们可以把它叫做“未来可期，活在当下”策略！

我们一天一天地来审视这个计划。在第 i 天，我们面临一个抉择：今天的力量够不够用呢？

如果力量足够 (current_strength >= X[i])：太棒了！今天不用破费了。但是，今天这瓶价格为 C[i] 的饮料，我们虽然现在不买，但它成了一个“备选项”。万一以后哪天力量不够了，我们可以回头“购买”这瓶我们曾经遇到的、便宜的饮料。
如果力量不足 (current_strength < X[i])：呜喵... 遇到困难了！我们必须喝饮料来增强力量，否则今天的目标就完不成了。
- 需要喝多少瓶呢？ 我们差了 deficit = X[i] - current_strength 的力量。每瓶饮料能增加 A 的力量，所以我们至少需要 ceil(deficit / A) 瓶。在C++整数运算里，这个“向上取整”可以漂亮地写成 (deficit + A - 1) / A 哦！
- 买哪些瓶呢？ 这就是贪心策略最闪光的地方！既然饮料的效果是永久的，我们当然应该选择 到目前为止我们遇到的所有饮料中，最便宜的那几瓶！比如说，今天已经是第5天了，但第1天的饮料超级便宜，我们就可以假装“穿越”回去买下它，来解决今天的危机。

所以，我们的策略就是：

遍历每一天。
把当天的饮料价格，放进一个“备选饮料池”里。
只有在力量不足时，才从这个池子里捞出最便宜的饮料来“喝”，直到力量足够为止。

用什么来做这个“备选饮料池”最方便呢？当然是能自动排序，并且可以轻松取出最小值的容器啦！std::multiset (或者一个最小堆 priority_queue) 就是完美的选择！它能帮我们随时找到最便宜的饮料，喵~

如果某一天，我们需要的饮料数量，比池子里的备选饮料还多，那就说明我们无论如何也凑不够力量了，计划失败，输出 -1。

代码实现喵~

下面就是实现这个思路的完整代码啦，我已经加上了详细的注释，希望能帮助你理解每一行代码的作用哦！

cpp

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

// 一个让输入输出变快的小魔法，打比赛很有用喵~
void setup_io() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
}

int main() {
    setup_io();

    int n;
    long long k;
    std::cin >> n >> k;

    std::vector<long long> x(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> x[i];
    }

    long long a;
    std::cin >> a;

    std::vector<long long> c(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> c[i];
    }

    long long current_strength = k;
    long long total_cost = 0;
    // 这就是我们的“备选饮料池”，用 multiset 可以自动排序，方便我们找到最便宜的饮料！
    std::multiset<long long> available_costs;

    // 一天一天地过日子~
    for (int i = 0; i < n; ++i) {
        // 今天健身房的饮料，也成了一个新的备选项。
        // 我们把它加入备选池，以备不时之需。
        available_costs.insert(c[i]);

        // 检查当前力量是否足够完成今天的任务
        if (current_strength < x[i]) {
            // 计算力量差额
            long long deficit = x[i] - current_strength;
            
            // 计算需要喝多少瓶饮料才能弥补差额
            // (deficit + a - 1) / a 是向上取整的经典写法，确保力量足够
            long long needed_drinks = (deficit + a - 1) / a;

            // 检查我们的“备选池”里有没有足够的饮料
            if (available_costs.size() < static_cast<size_t>(needed_drinks)) {
                // 如果备选的饮料都不够，那计划就失败了，呜...
                std::cout << -1 << std::endl;
                return 0; 
            }

            // 贪心策略！从备选池里，选出 `needed_drinks` 瓶最便宜的饮料来“喝”
            for (long long j = 0; j < needed_drinks; ++j) {
                // *available_costs.begin() 就是最便宜饮料的价格
                total_cost += *available_costs.begin();
                // 喝掉了，就要从备选池里移除
                available_costs.erase(available_costs.begin());
            }

            // 喝完饮料，力量变强了！
            current_strength += needed_drinks * a;
        }
    }

    // 成功完成所有计划，输出总花费！
    std::cout << total_cost << std::endl;

    return 0;
}

复杂度分析的说

时间复杂度: O(N log N) 的说。我们有一个遍历 N 天的主循环。在循环内部，最耗时的操作是与 multiset 的交互。insert() 操作和 erase(begin()) 操作的时间复杂度都是 O(log S)，其中 S 是 multiset 中元素的数量。因为 multiset 的大小最多为 N，所以这些操作的复杂度可以看作是 O(log N)。我们总共会执行 N 次插入，以及最多 N 次删除。所以总的时间复杂度就是 O(N log N) 啦。
空间复杂度: O(N) 的说。我们用了几个 vector 来存储输入数据，这占用了 O(N) 的空间。multiset available_costs 在最坏的情况下（一瓶饮料都不买）会存储 N 个价格，也占用 O(N) 的空间。所以总的空间复杂度是 O(N)。

知识点与总结喵~

这道题真是一道美味的贪心小鱼干！它教会了我们几个很重要的东西：

贪心思想的应用: 核心是“延迟决策”和“局部最优”。我们不急于购买饮料，只有在力量不足的“最后关头”才被迫购买。而一旦决定购买，我们总是选择当前代价最小的方案（最便宜的饮料），从而导向全局最优解。
合适的数据结构: std::multiset 在这里大放异彩！它能自动维护一个有序的集合，让我们能以 O(log N) 的效率轻松完成“加入备选项”和“取出最便宜的”这两个核心操作。用 std::priority_queue（最小堆）也能达到同样的效果，而且通常会更快一点点哦。
细节处理:
- 向上取整: 计算 needed_drinks 时， (deficit + a - 1) / a 这个小技巧非常实用，一定要记住它！
- 永久效果: 理解“永久增加”是解题的关键。这让我们不必局限于当天购买饮料，而是可以从所有过去的日子里选择最优的方案。
- 数据类型: 力量和花费都可能很大，记得使用 long long 防止数据溢出，这可是竞赛中的好习惯呐！

希望这篇题解能让你对贪心算法有更深的理解！继续努力，下一道题也一定能轻松解决的，加油喵！(ฅ'ω'ฅ)

F. Workout plan - 题解 ​

比赛与标签 ​

题目大意喵~ ​

贪心思路大揭秘！ ​

代码实现喵~ ​

复杂度分析的说 ​

知识点与总结喵~ ​