D. Flower Boy - 题解

比赛与标签

比赛: Codeforces Round 1020 (Div. 3) 标签: binary search, dp, greedy, two pointers, *1500 难度: *1500

喵喵，这是个什么任务呀？

主人，你好呀！今天我们来解决一个关于花园和鲜花的问题，听起来就很浪漫对不对，喵~

是这样的：我们有一个花园，里面有 n 朵花，每朵花都有一个美丽值 a_i。Igor 想要从左到右走过花园，并从中挑选出 m 朵花。他对这些花有特殊的要求哦：他挑出的第 i 朵花，其美丽值必须至少为 b_i。

有时候，花园里的花可能不够满足 Igor 的所有要求。不过别担心，我们有魔法！我们最多可以使用一次魔法棒，创造一朵任意美丽值为 k 的新花，并把它插在花园的任何位置。

我们的任务就是，找到能让 Igor 成功挑到 m 朵花的那个最小的魔法美丽值 k。如果不需要魔法就能成功，答案就是 0。如果就算用了魔法也还是不行，那只能遗憾地回答 -1 啦，呜...

来和本喵一起想想办法吧！

这个问题看起来有点复杂，但别怕，本喵会一步步带你解开它的谜底，喵~

第一步：不需要魔法棒的简单情况

首先，我们来考虑最简单的情况：万一我们根本不需要用魔法棒呢？这要怎么判断呀？

我们可以用一个很直观的 贪心策略 呐！Igor 是从左到右挑花的，所以为了满足第 i 个要求 b_i，他肯定会选择花园里满足 a[p] >= b_i 的、最靠左的那一朵花（当然，这朵花必须在他为满足第 i-1 个要求而挑选的花的右边）。

所以，我们可以用一个指针 a_ptr 指向花园里的花，另一个循环遍历要求 b_1, b_2, ..., b_m。对于每个要求 b_i，我们就从 a_ptr 当前的位置开始向右寻找，找到第一朵美丽值不小于 b_i 的花。如果能为所有 m 个要求都找到对应的花，那就太棒啦！说明我们不需要魔法，答案就是 0！

第二步：魔法棒的真正力量！

如果上面的贪心策略失败了，就轮到我们的魔法棒登场了！魔法棒可以创造一朵美丽值为 k 的花。为了让 k 最小，我们肯定不会浪费魔法，对吧？如果我们决定用魔法花来满足第 i 个要求 b_i，那么我们创造的花的美丽值恰好等于 b_i 就是最划算的，这样 k 才可能最小。

所以，问题就转化成了：我们应该 “跳过” 哪个要求 b_i，然后用我们创造的魔法花来满足它呢？我们的目标是，在所有可能的“跳过”方案中，找到那个 b_i 最小的。

第三步：前后缀分解的绝妙思路！

这可是解题的关键哦，要听仔细了喵！

如果我们决定用魔法花来满足第 i 个要求 b_i，这意味着我们需要在原始花园里找到 m-1 朵花，来满足剩下的两组要求：

1. 前缀要求: b_1, b_2, ..., b_{i-1}
2. 后缀要求: b_{i+1}, b_{i+2}, ..., b_m

由于 Igor 是从左到右挑花的，所有用来满足前缀要求的花，必须位于所有用来满足后缀要求的花的左边。它们之间不能有交叉！

这启发我们，可以预处理一些信息来快速判断这种“分割”是否可行。

1. 从左到右的贪心预处理 (L数组) 我们创建一个数组 L。L[i] 表示：如果我们要满足前缀要求 b_1, ..., b_i，采用从左到右的贪心策略，那么满足第 i 个要求 b_i 的那朵花在花园 a 中的（从1开始的）下标是多少。我们可以用一个指针在 O(n+m) 的时间内计算出所有 L[i] 的值。如果某个前缀无法满足，我们可以记一个特殊值（比如 n+1）。

2. 从右到左的贪心预处理 (R数组) 同理，我们再创建一个数组 R。R[i] 表示：如果我们要满足后缀要求 b_i, ..., b_m，采用从右到左的贪心策略（即为 b_m 找最右的花，然后为 b_{m-1} 找它左边最右的花...），那么满足第 i 个要求 b_i 的那朵花在花园 a 中的（从1开始的）下标是多少。我们同样可以在 O(n+m) 时间内计算出所有 R[i]。如果某个后缀无法满足，我们可以记一个特殊值（比如 0）。

第四步：组合起来，找到答案！

有了 L 和 R 这两个强大的数组，问题就迎刃而解啦！

我们遍历每一个可能被“跳过”的要求 b_i (从 i=1 到 m)。 对于一个给定的 i：

• 我们需要满足前缀 b_1, ..., b_{i-1}。根据我们的 L 数组，满足这个前缀所需要的最后一朵花在 L[i-1] 位置。
• 我们需要满足后缀 b_{i+1}, ..., b_m}。根据我们的 R 数组，满足这个后缀所需要的第一朵花在 R[i+1] 位置。

要让这个方案可行，前缀的最后一朵花必须在后缀第一朵花的左边，也就是 L[i-1] < R[i+1]。

如果这个条件成立，说明跳过 b_i 是一个可行的方案！这个方案需要创造的魔法花的美丽值是 b[i-1]。我们就用它来更新我们的最小 k 值。

把所有可能的 i 都检查一遍，找到的最小的那个 b[i-1] 就是我们的最终答案啦！如果遍历完发现没有一个 i 满足条件，那就说明即使用了魔法也无能为力，答案就是 -1。

本喵的代码时间！

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

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

    // L[i] 存储的是：从左到右贪心满足前 i 个要求时，第 i 个要求 b[i-1] 对应花朵在 a 中的 1-based 下标
    // L[0] 作为哨兵，表示在所有花之前
    std::vector<int> L(m + 1);
    L[0] = 0;
    int a_ptr = 0; // a数组的指针 (0-based)
    for (int i = 1; i <= m; ++i) {
        // 为第 i 个要求 b[i-1] 寻找花园 a 中第一朵满足条件的花
        while (a_ptr < n && a[a_ptr] < b[i - 1]) {
            a_ptr++;
        }
        // 如果找不到，说明这个前缀以及更长的前缀都无法满足
        if (a_ptr == n) {
            for (int j = i; j <= m; ++j) {
                L[j] = n + 1; // 标记为不可能
            }
            break;
        }
        L[i] = a_ptr + 1; // 记录 1-based 下标
        a_ptr++;          // 这朵花被用了，指针后移
    }

    // 首先检查不使用魔法棒的情况
    if (L[m] <= n) {
        std::cout << 0 << "\n";
        return;
    }

    // R[i] 存储的是：从右到左贪心满足后缀要求 b[i-1]...b[m-1] 时，第 i 个要求 b[i-1] 对应花朵在 a 中的 1-based 下标
    // R[m+1] 作为哨兵，表示在所有花之后
    std::vector<int> R(m + 2);
    R[m + 1] = n + 1;
    a_ptr = n - 1; // a数组的指针 (0-based), 从右开始
    for (int i = m; i >= 1; --i) {
        // 为第 i 个要求 b[i-1] 寻找花园 a 中最后一朵满足条件的花
        while (a_ptr >= 0 && a[a_ptr] < b[i - 1]) {
            a_ptr--;
        }
        // 如果找不到，说明这个后缀以及更短的后缀都无法满足
        if (a_ptr < 0) {
            for (int j = i; j >= 1; --j) {
                R[j] = 0; // 标记为不可能
            }
            break;
        }
        R[i] = a_ptr + 1; // 记录 1-based 下标
        a_ptr--;          // 这朵花被用了，指针前移
    }

    long long min_k = -1;

    // 遍历每一个要求 b[i-1]，尝试“跳过”它
    for (int i = 1; i <= m; ++i) {
        // 要跳过第 i 个要求，我们需要能满足前缀 b_1..b_{i-1} 和后缀 b_{i+1}..b_m
        // 满足前缀的最后一朵花下标是 L[i-1]
        // 满足后缀的第一朵花下标是 R[i+1]
        // 如果 L[i-1] < R[i+1]，说明前缀和后缀的花没有冲突，方案可行！
        if (L[i - 1] < R[i + 1]) {
            long long current_k = b[i - 1]; // 这个方案的成本就是 b[i-1]
            if (min_k == -1 || current_k < min_k) {
                min_k = current_k;
            }
        }
    }

    std::cout << min_k << "\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) 的说。我们计算 L 数组时，a_ptr 和循环变量 i 都只从头到尾走了一遍，所以是 O(N+M)。计算 R 数组同理。最后寻找答案的循环是 O(M)。所以每个测试用例的总时间复杂度是线性的，超级快，喵！
• 空间复杂度: O(N+M) 的说。我们需要空间来存储输入的数组 a 和 b，以及我们自己创建的辅助数组 L 和 R。

这次学到了什么喵？

这道题真的很有趣，融合了好几种思想呢！

1. 贪心策略: 无论是检查初始情况，还是预处理 L 和 R 数组，我们都用到了贪心思想，总是选择最左边或最右边可行的花。
2. 预处理与前后缀分解: 解决问题的核心在于将“插入一个元素”转化为“跳过一个要求”。通过预处理前后缀的贪心结果，我们可以 O(1) 地判断跳过某个要求是否可行，这是非常高效的技巧！
3. 双指针: 在计算 L 和 R 数组时，我们实际上使用了双指针的思想，一个指针遍历要求，一个指针遍历花园，避免了嵌套循环，大大降低了时间复杂度。
4. 边界处理: 使用哨兵值（L[0] 和 R[m+1]）以及不可能的标记（n+1 或 0）能让我们的代码逻辑更清晰，避免了繁琐的边界条件判断，是个很棒的编程习惯，喵~

希望本喵的讲解对你有帮助哦！继续加油，算法的世界还有更多有趣的冒险在等着我们呢！喵~