D. This Is the Last Time - 题解

比赛与标签

比赛: Codeforces Round 1037 (Div. 3) 标签: data structures, greedy, sortings 难度: *1200

题目大意喵~

主人你好呀~！这道题是说，我们一开始有 k 枚金币，面前有 n 家赌场，喵。

每家赌场 i 都有三个属性：

l_i：进入所需的最少金币。
r_i：进入所能拥有的最多金币。
real_i：玩过之后，你的金币数量会变成 real_i。

也就是说，如果你当前有 x 枚金币，只有当 l_i <= x <= r_i 时，你才能进入第 i 家赌场。玩过之后，你的金币就变成了 real_i。

我们可以按任意顺序去不同的赌场，但每家赌场最多只能去一次。我们的目标是，通过聪明地选择去的赌场和顺序，最后能得到的金币数量最大是多少呢？快来帮帮我吧，喵~

解题思路大揭秘！

这道题看起来有点复杂，因为我们可以选择去哪个赌场，顺序也很自由。这种时候，我们就要想想，在任何一个时间点，做什么样的选择才是最棒的呢？这通常就是贪心算法的信号啦，喵！

贪心策略的思考

假设我们现在有 current_k 枚金币，我们能去哪些赌场呢？当然是所有满足 l_i <= current_k <= r_i 的赌场啦。在这些可以选择的赌场里，我们应该去哪一个呢？

一个很自然的想法是：去那个能让我们钱变得最多的赌场！也就是选择 real_i 最大的那一个。为什么呢？因为拥有更多的金币，就意味着我们将来有可能解锁更多准入门槛 (l_i) 更高的赌场，从而获得更大的收益，对吧？

如何高效实现贪心？

如果我们每次都遍历所有 n 个赌场来找可以去的、并且 real_i 最大的那个，效率太低啦，肯定会超时的说。所以我们需要更聪明的办法！

这就是“排序 + 优先队列”这个黄金组合大显身手的时候了，喵！

排序 (Sorting) 我们首先可以把所有的赌场按照准入门槛 l_i 从小到大排个序。这样做的好处是，随着我们手里的金币 current_k 越来越多，我们能进入的赌场也是一个逐渐扩大的集合。我们只需要按顺序检查排好序的赌场列表，而不用每次都看全部，效率就高多啦。
优先队列 (Priority Queue) 我们需要一个“百宝袋”来存放所有我们当前有能力进入的赌场，并且能快速地从中挑出 real_i 最大的那个。这不就是**最大优先队列（Max Heap）**最擅长的工作嘛！

算法流程

结合排序和优先队列，我们的解题步骤就清晰了喵~

准备工作：先把所有赌场按照 l_i 从小到大排序。准备一个最大优先队列 pq，用来存放 {real_i, r_i} 对。
主循环：我们不断地进行决策，直到不能再玩为止。
- 步骤一：更新候选赌场 检查一下排好序的赌场列表，把所有当前金币 current_k 已经足够进入（即 l_i <= current_k）的赌场，都丢进我们的优先队列 pq 里。
- 步骤二：清理过时赌场 优先队列里可能有一些赌场，虽然我们以前能进，但现在因为金币太多了（current_k > r_i），反而进不去了。我们需要把这些“过时”的赌场从队首请出去。
- 步骤三：做出贪心选择 清理完毕后，如果优先队列是空的，说明没有可以玩的赌场了，我们就只能停手啦，循环结束。如果非空，队首的那个赌场就是我们当前能玩的、且 real_i 最大的选择！毫不犹豫地选择它！
- 步骤四：更新状态 玩了这家赌场后，我们的金币数量更新为它的 real_i。同时，我们要随时记录下我们曾经拥有过的最大金币数 max_k，因为题目问的是能得到的最大数量，我们可以在任何一步停下来保留当前成果。
重复循环：回到步骤一，用新的金币数量去解锁更多的赌场，如此循环往复。

最后，记录下来的 max_k 就是我们的答案啦！这个方法保证了我们每一步都做出了局部最优的选择，最终汇集成了全局最优解，喵~

代码实现喵~

cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

// 用一个结构体来存放赌场的信息，更清晰明了喵
struct Casino {
    long long l, r, real;
};

// 自定义比较函数，用于给赌场按 l_i 从小到大排序
bool compareCasinos(const Casino& a, const Casino& b) {
    if (a.l != b.l) {
        return a.l < b.l;
    }
    // 如果 l 相同，可以加一些次要排序规则，让行为更确定
    if (a.r != b.r) {
        return a.r < b.r;
    }
    return a.real > b.real;
}

void solve() {
    int n;
    long long k;
    std::cin >> n >> k;
    std::vector<Casino> casinos(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> casinos[i].l >> casinos[i].r >> casinos[i].real;
    }

    // 步骤一：按照 l_i 从小到大排序
    std::sort(casinos.begin(), casinos.end(), compareCasinos);

    long long current_k = k;
    long long max_k = k; // 记录整个过程中出现过的最大金币数
    int casino_ptr = 0; // 一个指针，指向下一个要考虑的赌场

    // 最大优先队列，存放 {奖励金币, 进入上限} 对，自动按奖励金币从大到小排
    std::priority_queue<std::pair<long long, long long>> pq;

    while (true) {
        // 步骤一：将所有当前金币数能满足 l_i 条件的赌场加入优先队列
        while (casino_ptr < n && casinos[casino_ptr].l <= current_k) {
            pq.push({casinos[casino_ptr].real, casinos[casino_ptr].r});
            casino_ptr++;
        }

        // 步骤二：从优先队列顶部移除那些 r_i < current_k 的过时赌场
        while (!pq.empty() && pq.top().second < current_k) {
            pq.pop();
        }

        // 步骤三：如果队列为空，说明没有可以玩的赌场了，结束循环
        if (pq.empty()) {
            break;
        }

        // 步骤三（续）：队首就是当前最优选择！
        auto best_casino = pq.top();
        pq.pop();
        
        // 步骤四：玩这家赌场，更新金币数量
        current_k = best_casino.first;
        
        // 随时更新我们能达到的最大金币数
        max_k = std::max(max_k, current_k);
    }

    std::cout << max_k << std::endl;
}

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 N) 的说。
- 首先，对 n 个赌场进行排序，需要 O(N log N) 的时间。
- 在主循环中，每个赌场最多被 push 进优先队列一次，也最多被 pop 出一次。每次 push 或 pop 的操作复杂度是 O(log N)。
- 所以，所有优先队列操作的总时间复杂度是 O(N log N)。
- 两者相加，总的时间复杂度就是 O(N log N) 啦。
空间复杂度: O(N) 的说。
- 我们需要一个 vector 来存储 n 个赌场的信息，这需要 O(N) 的空间。
- 在最坏的情况下，优先队列可能会存储所有 n 个赌场，所以也需要 O(N) 的空间。
- 因此，总的空间复杂度是 O(N)。

知识点与总结

这道题真是一次有趣的冒险，不是吗？它教会了我们几件重要的事情，喵~

贪心思想: 当面临一系列选择时，思考每一步的“局部最优解”是否能导向“全局最优解”。在这里，每次都选能让钱变得最多的赌场就是很棒的贪心策略。
“排序 + 优先队列”模式: 这是一个非常经典的组合！当问题涉及“随着某个值的增长，不断有新选项解锁”时，就可以用这个模式。
- 排序：用来预处理数据，使得我们可以顺序地、不遗漏地考虑新解锁的选项。
- 优先队列：用来动态地维护当前所有可选的选项，并快速找到最优的那个。
状态更新与记录: 在解题过程中，要分清“当前状态”（比如 current_k）和“需要记录的最优结果”（比如 max_k）。我们是在用当前状态做决策，但最终答案可能是过程中的某个峰值。

主人要记住这个“排序 + 优先队列”的组合拳哦，它在处理这类需要按条件解锁并进行贪心选择的问题时超级好用！多练习就能掌握啦，加油喵~！

D. This Is the Last Time - 题解 ​

比赛与标签 ​

题目大意喵~ ​

解题思路大揭秘！ ​

代码实现喵~ ​

复杂度分析 ​

知识点与总结 ​