Constructing the Array - 题解

比赛与标签

比赛: Codeforces Round 642 (Div. 3) 标签: constructive algorithms, data structures, sortings 难度: *1600

Nya-ice to Meet You, Little Problem! 喵~

主人你好呀~！遇到了一道有趣的构造题吗？别担心，让本猫娘陪你一起把它解决掉吧！

这道题是这样子的：我们有一个长度为 n 的数组，一开始里面全都是 0。然后我们要进行 n 次操作，从第 1 次到第 n 次。

在第 i 次操作中，我们要：

1. 找到一个最长的、只包含 0 的连续子数组。
2. 如果有好几个这样一样长的子数组，我们就选最靠左边的那一个。
3. 假设我们选中的这个子数组是 [l, r]。我们要在这个子数组的正中间填上数字 i。
   • 如果子数组的长度 r - l + 1 是奇数，中间位置就是 (l+r)/2。
   • 如果长度是偶数，中间位置就是 (l+r-1)/2 (也就是偏左的那个中心点)。

我们的任务就是，在完成所有 n 次操作后，告诉大家这个数组最终变成了什么样子。听起来是不是像一个有趣的游戏呢？喵~

Cat's Strategy: The Priority Queue Magic! ✨

要解决这个问题，关键在于每次都能快速找到那个“最长且最靠左”的 0 段，对吧？

如果我们每次都去遍历整个数组来找，那也太慢了，肯定会超时的说！( TДT) 所以我们需要一个更聪明的办法。

这时候，就轮到我们的魔法道具——优先队列（Priority Queue）——登场啦！

优先队列就像一个神奇的收纳盒，你每次放东西进去，它都会自动帮你排好序，让你每次都能拿到“最重要”的那个！

在这个问题里，什么是最重要的呢？当然是最长的 0 段啦！如果长度一样，那就是最靠左（起始下标最小）的那个。

所以，我们可以这样定义我们优先队列的排序规则：

1. 长度为第一优先级，长度越长越优先。
2. 起始下标为第二优先级，下标越小越优先。

C++ 的 std::priority_queue 默认是一个大顶堆，它会把最大的元素放在队首。这正好满足了我们“长度越长越优先”的需求！可是，对于“起始下标越小越优先”，它就有点力不从心了。

但是，聪明的猫娘有办法！我们可以耍个小花招：把起始下标存成它的负数！这样一来，起始下标 l 越小，它的负数 -l 就越大。大顶堆就会优先选择 -l 大的那个，这不就等于选择了 l 小的那个嘛？是不是很机智，喵哈哈~

所以，我们可以在优先队列里存储一个 pair，形如 {length, -start_index}。

整个流程就清晰起来啦：

1. 一开始，整个数组 [1, n] 都是 0，所以我们把 {n, -1} 这个代表初始 0 段的元素放进优先队列。
2. 我们进行 n 次循环，代表 n 次操作。
3. 在第 i 次操作中： a. 从优先队列的队首取出一个元素，这就是当前“最长且最靠左”的 0 段。 b. 根据它的长度和起始位置，计算出中心点 mid，然后在答案数组的 ans[mid] 位置填上 i。 c. 这个 0 段被 mid 分成了两部分：左边的 [l, mid-1] 和右边的 [mid+1, r]。 d. 如果这两部分新产生的 0 段长度大于 0，就把它们也变成 {length, -start_index} 的形式，放回优先队列里。
4. 循环 n 次后，所有位置都被填满了，我们的答案数组也就构造完成啦！

这样一来，我们每次都能在 O(log n) 的时间里找到我们想要的 0 段，是不是超级高效呀！

Let's Get Our Paws Dirty with Code! 🐾

好啦，思路已经很清晰了，现在就让我们把想法变成代码吧！本猫娘已经帮你加上了详细的注释哦~

#include <iostream>
#include <vector>
#include <queue>
#include <utility>

void solve() {
    int n;
    std::cin >> n;
    // 为了和题目描述的下标保持一致，我们使用从1开始的下标，喵~
    std::vector<int> ans(n + 1);

    // 这个优先队列用来存放所有0段的信息
    // 每个元素是一个pair: {长度, -起始下标}
    // 我们用 -起始下标 是因为 std::priority_queue 是大顶堆。
    // 为了在长度相同时，能选出起始下标最小的段，
    // 我们需要让 -起始下标 最大化，这正好是大顶堆的功能！
    std::priority_queue<std::pair<int, int>> pq;

    // 一开始，整个数组都是一个0段，从1到n
    pq.push({n, -1});

    // 我们要进行n次操作，每次填入一个数字
    for (int i = 1; i <= n; ++i) {
        // 取出当前最符合条件的0段（最长，然后最靠左）
        std::pair<int, int> top = pq.top();
        pq.pop();

        int len = top.first;
        int l = -top.second; // 恢复成真实的起始下标（1-based）
        int r = l + len - 1;

        int mid;
        // 根据0段长度的奇偶性来计算中心点
        if (len % 2 != 0) { // 奇数长度
            mid = (l + r) / 2;
        } else { // 偶数长度
            mid = (l + r - 1) / 2;
        }

        // 在计算出的中心位置填上当前的数字i
        ans[mid] = i;

        // 原来的0段 [l, r] 被新填入的数字分成了两段。
        // 如果这两段新的0段长度不为0，就把它们也加入优先队列里。

        // 左边的0段: [l, mid - 1]
        if (l <= mid - 1) {
            pq.push({(mid - 1) - l + 1, -l});
        }
        
        // 右边的0段: [mid + 1, r]
        if (mid + 1 <= r) {
            pq.push({r - (mid + 1) + 1, -(mid + 1)});
        }
    }

    // 打印最终的答案数组
    for (int i = 1; i <= n; ++i) {
        std::cout << ans[i] << (i == n ? "" : " ");
    }
    std::cout << "\n";
}

int main() {
    // 加速一下输入输出，让程序跑得像小猫一样快！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

How Fast is Our Kitty-Code? 🚀

• 时间复杂度: O(n log n) 的说 我们总共要进行 n 次操作来填满数组。在每一次操作中，我们都要从优先队列里取出一个元素 (pop)，并可能放入两个新元素 (push)。优先队列中的元素数量最多是 O(n) 级别的，所以每一次 push 或 pop 操作的时间复杂度都是 O(log n)。因此，总的时间复杂度就是 n 次操作乘以每次操作的 log n，即 O(n log n)。对于这道题的数据范围来说，是完全足够快的！

• 空间复杂度: O(n) 的说 我们需要一个长度为 n 的数组 ans 来存储答案，这占用了 O(n) 的空间。优先队列在最坏的情况下，可能会存储大约 n/2 个 0 段（想象一下每次都从中间完美地分开），所以它占用的空间也是 O(n)。总的空间复杂度就是 O(n) 啦。

Purr-fect Takeaways! 📚

通过解决这道题，我们又学到了很多东西呢，真棒！

1. 核心数据结构: 优先队列（Heap） 是解决这类“反复选取最优元素”问题的神器！当题目要求你每次都从一个动态变化的集合中找出最大/最小/最优先的元素时，一定要先想到它，呐。

2. 排序小技巧: 在使用大顶堆处理“第一关键字最大，第二关键字最小”这类问题时，把第二关键字存为负数是一个非常经典和实用的技巧！一定要记住哦~

3. 问题分解: 这个题目本质上是一个模拟过程。我们成功地将“找到最长最左的 0 段”这个核心步骤，通过优先队列进行了优化，把一个看似复杂的过程，分解成了 n 次简单、重复的操作。

希望这篇题解能帮到你！继续加油，享受每一道题带来的挑战和乐趣吧！本猫娘会一直为你加油的，喵~ (ฅ'ω'ฅ)