Moe's CF Life

Appearance

E. Min Max MEX - 题解 ​

比赛与标签 ​

比赛: Codeforces Round 1016 (Div. 3) 标签: binary search, brute force, greedy, *1500 难度: *1500

题目大意喵~ ​

主人你好呀~！这道题是这样的呐：

我们拿到一个长度为 n 的数组 a 和一个整数 k。我们的任务是把这个数组 a 切成 k 个连续并且不重叠的小段（子数组），这些小段拼起来要刚好是完整的数组 a。

对于每个小段，我们都可以计算它的 MEX 值。MEX(v) 就是指在数组 v 中 没有出现过的最小非负整数。比如说，MEX({0, 1, 3, 4}) 就是 2 啦，因为 0 和 1 都在，但 2 不在。

我们的最终目标，是找到一种切分方法，使得这 k 个小段的 MEX 值中的 最小值 尽可能地 大。最后输出这个最大的最小值就可以啦！听起来是不是很有趣喵？(ฅ'ω'ฅ)

解题思路大揭秘！ ​

这道题要求我们“最大化一个最小值”，一看到这种问法，我们的脑海里就应该闪过一道光——二分答案！这可是解决这类问题的经典套路哦，喵~

核心思想：二分答案 ​

我们可以不直接去求那个最大的最小值，而是换个问法：“我们能不能找到一种切分方法，使得所有子数组的 MEX 值都 至少 是 x 呢？”

这个问题就变成了一个判断题，回答“能”或“不能”就可以啦。如果对于某个 x 我们能做到，那么对于所有比 x 小的值，肯定也都能做到。反之，如果连 x 都做不到，那比 x 更大的值就更不可能了。这种单调性正是二分答案的完美应用场景！

所以，我们可以在一个可能的 x 的范围里（比如 0 到 n+1）进行二分查找，找到那个最大的、可以满足条件的 x。

check(x) 函数的设计 ​

现在，问题的核心就转移到了如何实现这个 check(x) 函数上。

check(x) 的目标是：判断是否存在一种切分，能把原数组 a 分成 k 个子数组，且每个子数组的 MEX 都 >= x。

一个子数组的 MEX 要想 >= x，需要满足什么条件呢？根据 MEX 的定义，这意味着这个子数组必须 包含所有从 0 到 x-1 的整数。

贪心策略 ​

好啦，现在我们的任务变成了：在数组 a 中，找到 至少 k 个 不重叠的、并且都包含了 0, 1, ..., x-1 所有整数的连续子数组。

为了能找到尽可能多的这种子数组，我们应该采用贪心策略！也就是说，我们找到的每一个符合条件的子数组，都应该是 尽可能短 的。这样才能给后面的部分留出更多空间，去寻找下一个符合条件的子数组，对吧？

所以我们的贪心策略是：

  1. 从数组的开头（比如 current_pos = 0）开始。
  2. 找到从 current_pos 开始的、最短的、包含了 0 到 x-1 的子数组。假设这个子数组的结尾是 end_pos。
  3. 如果能找到，我们的计数器就 +1，然后从 end_pos + 1 的位置继续寻找下一个。
  4. 重复这个过程，直到扫描完整个数组。
  5. 最后，看看我们找到的子数组数量是不是 >= k。如果是，check(x) 就返回 true，否则返回 false。

如何高效地贪心？请出我们的好朋友——线段树！ ​

贪心策略中最关键的一步，就是“找到从 current_pos 开始的最短的符合条件的子数组”。这个子数组的终点 end_pos，其实就是所有 0, 1, ..., x-1 这些数字在 current_pos 之后首次出现的位置中，最靠右的那一个。

每次都去暴力查找这些位置太慢啦，会让 check(x) 的复杂度爆炸的说！我们需要一个更聪明的办法。

我们可以预处理一个数组 f_arr，其中 f_arr[i] 表示：从位置 i 开始，要包含 0 到 x-1，子数组最少需要延伸到哪个位置。

这个 f_arr 怎么算呢？我们可以从后往前遍历数组 a（从 n-1 到 0）。在遍历到 i 时，f_arr[i] 的值就等于 0 到 x-1 这些数字在 i 或 i 之后出现位置的最大值。

为了快速查询“一组数字出现位置的最大值”，线段树 就闪亮登场啦！

  • 我们可以建一棵线段树，维护每个数字（0 到 n）最后一次出现的位置。
  • 当我们从后往前遍历到 i 时，如果 a[i] 的值小于 x，我们就更新线段树中 a[i] 这个“键”对应的值为 i。
  • 然后，我们查询线段树上 [0, x-1] 这个区间的最大值，这个最大值就是我们想要的 f_arr[i]！

这样，我们就可以在 O(n log n) 的时间内预处理出 f_arr，然后再用 O(n) 的时间进行贪心扫描，check(x) 的总复杂度就是 O(n log n)。

结合外层的二分查找 O(log n)，整个算法的总时间复杂度就是 O(n log^2 n)，对于这道题的 n 的总和限制来说，是完全可以接受的！

AC 代码实现喵~ ​

cpp
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

// 使用全局变量来避免在每个测试用例中重复分配内存，可以提高效率喵~
std::vector<int> seg_tree;
std::vector<int> f_arr;
std::vector<bool> is_present;

// 线段树更新操作：在node节点表示的区间[start, end]中，更新下标idx的值为val
void update_tree(int node, int start, int end, int idx, int val) {
    if (start == end) {
        seg_tree[node] = val;
        return;
    }
    int mid = start + (end - start) / 2;
    if (start <= idx && idx <= mid) {
        update_tree(2 * node, start, mid, idx, val);
    } else {
        update_tree(2 * node + 1, mid + 1, end, idx, val);
    }
    // 父节点的值是左右子节点的最大值
    seg_tree[node] = std::max(seg_tree[2 * node], seg_tree[2 * node + 1]);
}

// 线段树查询操作：查询区间[l, r]内的最大值
int query_tree(int node, int start, int end, int l, int r) {
    if (r < start || end < l || l > r) {
        return -1; // 表示无效区间
    }
    if (l <= start && end <= r) {
        return seg_tree[node];
    }
    int mid = start + (end - start) / 2;
    int p1 = query_tree(2 * node, start, mid, l, r);
    int p2 = query_tree(2 * node + 1, mid + 1, end, l, r);
    return std::max(p1, p2);
}

// 检查是否能找到一种划分，使得所有子数组的MEX都至少为x
bool check(int x, int n, int k, const std::vector<int>& a) {
    // x=0是平凡情况，任何非空子数组的MEX都>=0
    if (x == 0) {
        return true;
    }
    
    // 如果0到x-1中任何一个数在整个数组中都不存在，那就不可能满足条件
    for (int i = 0; i < x; ++i) {
        if (!is_present[i]) {
            return false;
        }
    }

    // 初始化线段树，存储0到x-1这些数字最后出现的位置。初始为n表示还没见过。
    for (int i = 0; i < x; ++i) {
        update_tree(1, 0, n, i, n);
    }

    // 从后往前遍历，计算f_arr[i]
    // f_arr[i]表示从i开始的子数组，要包含0~x-1，最少要延伸到哪个位置
    for (int i = n - 1; i >= 0; --i) {
        if (a[i] < x) {
            // 更新a[i]这个数字最后出现的位置
            update_tree(1, 0, n, a[i], i);
        }
        // 查询[0, x-1]区间内所有数字最后出现位置的最大值
        f_arr[i] = query_tree(1, 0, n, 0, x - 1);
    }

    // 贪心策略：寻找k个符合条件的子数组
    int count = 0;
    int current_pos = 0;
    while (current_pos < n) {
        // 从current_pos开始的子数组，需要延伸到end_pos
        int end_pos = f_arr[current_pos];
        if (end_pos >= n) { // 如果end_pos>=n，说明从这里开始无法构成一个完整的集合了
            break;
        }
        count++; // 找到了一个
        current_pos = end_pos + 1; // 从下一个位置继续寻找
    }

    return count >= k;
}

void solve() {
    int n, k;
    std::cin >> n >> k;
    std::vector<int> a(n);
    is_present.assign(n + 1, false);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
        if (a[i] <= n) {
            is_present[a[i]] = true; // 记录0到n哪些数字出现过
        }
    }

    // 计算整个数组的MEX，作为二分答案的上界，是一个小优化
    int mex_a = 0;
    while (mex_a <= n && is_present[mex_a]) {
        mex_a++;
    }

    // 二分查找最大的可行x
    int low = 0, high = mex_a + 1, ans = 0;
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (check(mid, n, k, a)) {
            ans = mid; // mid是可行的，尝试更大的值
            low = mid + 1;
        } else {
            high = mid; // mid不可行，缩小范围
        }
    }
    std::cout << ans << '\n';
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int t;
    std::cin >> t;
    
    // 一次性分配足够大的内存
    seg_tree.resize(4 * (200000 + 2));
    f_arr.resize(200001);
    is_present.reserve(200002);

    while (t--) {
        solve();
    }
    return 0;
}

复杂度分析的说 ​

  • 时间复杂度: O(logN * (N logN))，也就是 O(N log²N) 的说。

    • 外层的二分答案需要 O(log N) 次 check 函数的调用。
    • check(x) 函数内部，最耗时的部分是使用线段树预处理 f_arr 数组。这个过程需要遍历数组 a 一次（O(N)），每次遍历都伴随着一次线段树的查询或更新（O(log N)）。所以 check 函数的复杂度是 O(N log N)。
    • 两者相乘，总时间复杂度就是 O(N log²N)。因为所有测试用例的 N 加起来有上限，这个复杂度是可以通过的~

  • 空间复杂度: O(N) 的说。

    • 我们需要一个数组 a 存储输入，大小为 O(N)。
    • 线段树 seg_tree 需要大约 4N 的空间，所以是 O(N)。
    • f_arr 和 is_present 数组也都是 O(N) 的空间。
    • 所以总的空间复杂度是 O(N)。

知识点与总结喵~ ​

这道题真是一次精彩的冒险！它教会了我们好几个重要的知识点呐：

  1. 二分答案: 这是解决“最大化最小值”或“最小化最大值”问题的神兵利器！当你看到这类关键词时，一定要优先想想能不能二分答案，把一个复杂的优化问题变成简单的判定问题。

  2. 贪心思想: 在判定是否能凑够 k 个子数组时，我们采用了“让每个子数组尽可能短”的贪心策略。正确的贪心是高效求解的关键。

  3. 线段树: 为了支撑我们的贪心策略，我们需要快速查询一个动态变化的区间最大值。线段树在这里就派上了大用场！它让我们能在对数时间内完成查询，大大优化了 check 函数的效率。

  4. 问题转化: 整个解题过程就是一个不断转化问题的过程。从“最大化最小值” -> “能否达到某个值 x” -> “能否找到 k 个包含 0..x-1 的子数组” -> “如何高效地找到这些子数组”。把大问题拆解成小问题，是算法竞赛中非常重要的能力哦！

希望这篇题解能帮到你，主人！下次遇到类似的题目，你一定也能轻松解决的！加油喵~ (๑•̀ㅂ•́)و✧

Released under the MIT License.

Copyright © 2024-present Moe