D. Yet Another Monster Killing Problem - 题解

比赛与标签

比赛: Educational Codeforces Round 76 (Rated for Div. 2) 标签: binary search, data structures, dp, greedy, sortings, two pointers 难度: *1700

喵喵，来读题啦！

主人，你好呀！今天我们来挑战一个有趣的怪物杀手问题，喵~

是这样的，我们有一个地下城，里面有 n 只怪物排成一队，每只怪物都有一个力量值 a[i]。而我们呢，拥有一支由 m 位英雄组成的强大队伍！每位英雄也有自己的力量 p 和耐力 s。

我们的目标是打败所有怪物，而且要用最少的天数！每天的流程是这样的：

1. 我们从英雄队伍里选 一位 英雄出战。
2. 这位英雄会从当前还没被打败的第一只怪物开始挑战。
3. 要打败一只怪物，英雄的力量 p 必须 大于或等于 怪物的力量 a。如果英雄不够强，他就会撤退，这一天就结束了。
4. 打败一只怪物后，英雄可以选择继续挑战下一只，或者离开。
5. 英雄在一天内最多只能打败 s 只怪物（也就是他的耐力值），或者打到没有怪物为止，然后这一天就结束了。

那么问题来了，最少需要多少天才能把所有怪物都清理干净呢？如果不可能完成，就告诉我们 -1 呐。

猫娘的贪心攻略喵~

这道题的目标是最小化天数，一看到“最小化”，我们通常会想到贪心或者动态规划，对吧？

在这里，一个非常自然的想法是：在每一天，我们都应该尽可能多地打败怪物。因为每天都要消耗一位英雄（也就是一天的时间），那让这一天变得“价值最大”，就是打败尽可能多的怪物！这个贪心策略听起来很不错，我们就顺着这个思路往下想，喵~

假设我们今天从第 i 只怪物开始打，我们想一口气打败 k 只怪物（也就是从第 i 只到第 i+k-1 只）。要做到这一点，需要满足什么条件呢？

1. 力量要足够：我们派出的英雄，他的力量必须比这 k 只怪物里 最强 的那一只还要强（或者相等）。设这 k 只怪物中的最大力量是 max_p，那么英雄的力量 p 必须 p >= max_p。
2. 耐力要足够：这位英雄的耐力 s 必须足以让他打败 k 只怪物，也就是 s >= k。

所以，对于一个怪物区间，我们需要找到一位英雄，同时满足这两个条件。

英雄们的潜力激发！

为了快速找到满足条件的英雄，我们得先对英雄数据做一点预处理，让他们随时准备好出战，喵！

1. 同力量英雄的最优选择：如果好几个英雄力量值相同，我们肯定会选耐力最高的那一个，对吧？用一个 std::map<int, int> 可以很方便地存下 力量 -> 最大耐力 的映射，还能自动按力量排序呢！

2. 力量与耐力的权衡：如果我们选了一个力量为 P 的英雄，那么任何力量比 P 更大的英雄其实也都能用。我们真正关心的是：对于一个最低力量要求 max_p，我们能找到的、所有力量不低于 max_p 的英雄中，耐力最高 的是多少？

为了解决这个问题，我们可以做一个小小的处理。先把英雄们按力量从小到大排序，然后从后往前遍历，更新每个英雄的耐力值，让 heroes[i].endurance = max(heroes[i].endurance, heroes[i+1].endurance)。这样处理完后，heroes[i] 的耐力值就代表了 所有力量不小于 heroes[i].power 的英雄中的最大耐力！是不是很神奇？这就叫后缀最大值，喵~

经过这样的预处理，对于任何一个力量要求 max_p，我们只需要用二分查找（比如 std::lower_bound）找到第一个力量不小于 max_p 的英雄，他所记录的耐力值就是我们能得到的最大耐力了！

模拟每一天！

准备工作完成，现在可以开始我们每天的屠龙之旅了！

我们用一个指针 i 记录当前打到哪只怪物了。

1. 开始新的一天，天数 days 加一。
2. 从第 i 只怪物开始，我们尝试组建一个当天要打的“怪物包”。设这个包里有 k 只怪物（从 i 到 i+k-1）。
3. 计算这个包里怪物的最大力量 max_p_chunk。
4. 用我们预处理好的数据，快速查询：要打败力量为 max_p_chunk 的怪物，我们能得到的最大耐力 s_avail 是多少。
5. 比较一下，如果 s_avail >= k，说明我们有能力打败这 k 只怪物！太棒了！我们贪心地尝试把下一只怪物（第 i+k 只）也加入这个包，继续循环。
6. 如果 s_avail < k，说明我们的英雄耐力不够了，打不了这么多。那么今天最多只能打 k-1 只怪物。这一天的工作就到此为止。
7. 更新 i，让它指向下一天要打的第一只怪物，然后开始新的一天。

特殊情况：不可能完成的任务

如果在某一天，我们连一只怪物都打不败（比如，尝试打第 i 只怪物，但找不到任何一个英雄比它强），那就说明任务不可能完成了，直接输出 -1 吧！在我们的循环里，这表现为内层循环一次都没能成功推进，i 的值没有变化。

代码魔法，变身！

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

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

    int m;
    std::cin >> m;
    // 使用 map 来存储每个力量值对应的最大耐力，顺便按力量排序
    std::map<int, int> power_to_max_s;
    for (int i = 0; i < m; ++i) {
        int p, s;
        std::cin >> p >> s;
        power_to_max_s[p] = std::max(power_to_max_s[p], s);
    }

    // 将 map 转换为 vector，方便后续处理
    std::vector<std::pair<int, int>> heroes;
    if (!power_to_max_s.empty()) {
        heroes.reserve(power_to_max_s.size());
        for (auto const& [p, s] : power_to_max_s) {
            heroes.push_back({p, s});
        }
        
        // 关键的预处理：计算耐力的后缀最大值
        // heroes[i].second 将表示力量 >= heroes[i].first 的所有英雄中的最大耐力
        for (int i = heroes.size() - 2; i >= 0; --i) {
            heroes[i].second = std::max(heroes[i].second, heroes[i + 1].second);
        }
    }

    // 一个 lambda 函数，用于快速查询：对于给定的最低力量要求，能得到的最大耐力是多少
    auto get_max_s = [&](int power) {
        if (heroes.empty()) {
            return 0; // 没有英雄，啥也干不了
        }
        // 使用二分查找找到第一个力量 >= power 的英雄
        auto it = std::lower_bound(heroes.begin(), heroes.end(), std::make_pair(power, 0));
        if (it == heroes.end()) {
            return 0; // 没有英雄的力量足够大
        }
        // 返回这个英雄（以及所有比他更强的英雄）能提供的最大耐力
        return it->second;
    };

    int days = 0;
    int i = 0; // i 是当前待处理的第一个怪物的索引
    while (i < n) {
        days++;
        int start_i = i; // 记录今天开始时打的怪物索引
        int max_p_chunk = 0; // 记录今天尝试打的这群怪物中的最大力量

        // 贪心：尝试在今天尽可能多地打怪
        while (i < n) {
            max_p_chunk = std::max(max_p_chunk, a[i]); // 更新怪物群的最大力量
            int k = i - start_i + 1; // 尝试打 k 只怪物
            int s_avail = get_max_s(max_p_chunk); // 查询打败这群怪物所需的最大可用耐力
            
            // 如果最强的英雄耐力都不够打 k 只，那今天就只能打 k-1 只了
            if (s_avail < k) {
                break;
            }
            // 如果耐力足够，就尝试把下一只怪物也加进来
            i++;
        }
        
        // 如果 i 没有前进，说明连第一只怪物都打不过，任务失败
        if (i == start_i) {
            std::cout << -1 << "\n";
            return;
        }
    }
    std::cout << days << "\n";
}

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+m) log m) 的说。

  • 首先，英雄预处理部分，用 map 插入是 O(m log m)。然后计算后缀最大值是 O(m)。
  • 接着是模拟打怪的过程。外层 while 循环最多执行 n 次（最坏情况每天打一个）。内层 while 循环的指针 i 在整个 solve 函数中只会从 0 遍历到 n 一次。在内层循环中，每次我们都会调用 get_max_s，它内部是一个二分查找，复杂度是 O(log m)。所以这部分总的复杂度是 O(n log m)。
  • 两部分加起来，总时间复杂度就是 O(m log m + n log m) 呐。

• 空间复杂度: O(n + m) 的说。

  • 我们需要存储 n 只怪物的力量，这是 O(n)。
  • 还需要存储最多 m 位英雄的信息（用 map 和 vector），这是 O(m)。
  • 所以总的空间开销是 O(n + m)。

猫娘的小课堂时间~

这道题真是一个很好的例子，告诉我们如何通过 贪心 + 预处理 来解决问题，喵~

• 核心思想：贪心。每天的目标都是最大化收益（打败最多的怪物）。
• 关键技巧：预处理英雄数据，特别是 后缀最大值 的思想，它把一个复杂的“查询最佳英雄”问题，变成了一个简单的二分查找问题。这大大优化了效率！
• 数据结构：std::map 在这里起到了去重、排序和初步聚合的作用。std::vector 配合 std::lower_bound 则是实现高效查询的利器。
• 注意事项：一定要想清楚边界情况和无解的情况！比如，如果没有任何英雄能打败当前怪物组里最弱的一只，那游戏就进行不下去了，要及时判断并输出 -1 哦。

只要思路清晰，一步步把问题拆解开，再难的题目也能解决的，主人要对自己有信心，加油喵！