连续数组 - 题解

标签与难度

标签: 排序, 数组处理, 实现, 贪心, 数据结构

难度: 1200

题目大意喵~

主人你好呀，喵~ 这道题是这样的：我们收到了 q 个小数组，每个数组里都有一些数字。我们的任务是，看看能不能把这 q 个数组里的所有数字，按照一定的顺序拼接成一个全新的大数组 A。

这个拼接有两个规矩哦：

1. 保持相对顺序：对于任何一个原来的小数组，它里面的数字在新数组 A 中的前后顺序不能变。比如说，如果一个小数组是 {5, 8}，那么在最终的 A 里面，5 也必须出现在 8 的前面，呐。
2. 最终是连续数组：拼接好的大数组 A 必须是一个“连续数组”。所谓的“连续数组”，就是指数组里的数字是严格连续递增的，后一个数恰好比前一个数大 1。比如 {2, 3, 4, 5} 就是一个完美的连续数组，而 {2, 3, 5} 就不是，因为它跳过了 4，喵~

如果能找到一种拼接方法满足这两个规矩，我们就输出 "YES"，否则就输出 "NO" 的说。

解题思路分析

嘿嘿，这道题看起来像是在玩拼图游戏呢，要把一堆小碎片拼成一幅完整的画！让我来分析一下怎么才能拼成功吧，喵~

要让最终合并成的大数组 A 是一个连续数组，比如 {min_val, min_val + 1, ..., max_val}，必须满足两个非常重要的条件。我们一个一个来看！

条件一：每个小数组内部必须是“好孩子”

想一想，最终的大数组 A 是一个严格递增的序列。如果我们在某个小数组里发现了一对数字 x 和 y，它本来的顺序是 [..., x, ..., y, ...]，但是 x > y。根据规则，x 必须出现在 y 的前面。可是在一个严格递增的连续数组里，小的值总是在大的值前面呀！这就出现矛盾了，对不对？

所以，我们得到的第一个关键结论是： 对于给定的 q 个小数组，每一个小数组内部的元素本身就必须是严格递增的。

比如，如果有一个小数组是 {8, 5}，那就不可能成功了，因为 8 必须在 5 前面，但在最终的连续数组里 5 肯定在 8 前面。所以，我们在读入数据的时候，就可以顺便检查一下每个小数组是不是都满足这个“严格递增”的性质。只要有一个不满足，就可以直接判定 "NO"，然后开心地结束啦，喵~

条件二：所有数字拼起来必须是“一家人”

好了，现在我们知道每个小数组内部都是乖乖递增的了。那把它们所有的数字都倒在一起，这个“大家庭”需要满足什么条件呢？

既然最终要拼成一个从 min_val 到 max_val 的无缝连接的连续序列，那说明：

1. 不能有重复的数字：如果所有数字里有两个 5，那它们就不可能组成连续数组了，因为连续数组里每个数字都是独一无二的。
2. 不能有空缺的数字：如果所有数字的最小值是 2，最大值是 6，但中间缺少了 4，那也拼不起来呀！

综合起来，第二个关键结论就是： 把所有小数组的全部元素汇集到一起，这个集合必须恰好是 min_val 到 max_val 之间所有的整数，每个数只出现一次。

怎么检查这个条件呢？一个超级简单又好用的方法就是：

1. 把所有数字都放进一个大大的容器里（比如一个 std::vector）。
2. 对这个容器进行排序！
3. 排序后，我们再从头到尾扫一遍。首先，第一个元素就是 min_val，最后一个就是 max_val。然后，我们检查相邻的两个数 v[i-1] 和 v[i]，是不是永远都满足 v[i] == v[i-1] + 1。如果对于所有的 i 都成立，那就说明这些数字既没有重复，也没有空缺，完美地构成了一个连续序列！只要有任何一个地方不满足，就说明这个“大家庭”有内部矛盾，直接判定 "NO"。

总结一下我们的策略：

1. 边读边查：在读入每个小数组时，检查它内部是否严格递增。如果不是，直接输出 "NO" 跑路。同时，把所有读到的数字都存到一个总的 vector 里。
2. 全局审查：如果所有小数组都通过了第一步的检查，我们就对存有所有数字的 vector 进行排序。
3. 最后确认：遍历排序后的 vector，检查相邻元素是否都相差 1。如果全部通过，恭喜主人，答案是 "YES"！否则就是 "NO"。

这个思路是不是很清晰呀？喵~ 就像我梳理毛发一样，先把局部理顺，再看整体光不光亮！

代码实现

这是我根据上面的思路，为主人精心准备的代码哦！注释写得很详细，希望能帮到你，呐~

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

// 为了让代码更整洁，把解题逻辑放在一个函数里喵~
void solve() {
    int q;
    std::cin >> q;

    std::vector<int> all_elements; // 用来存放所有数组的所有元素
    bool is_possible = true;       // 一个标志位，记录是否还可能成功

    // 循环读入 q 个数组
    for (int i = 0; i < q; ++i) {
        int k;
        std::cin >> k;

        if (k == 0) { // 如果是空数组，直接跳过就好啦
            continue;
        }

        int prev_element;
        std::cin >> prev_element;
        all_elements.push_back(prev_element);

        // 读入当前数组的剩余元素
        for (int j = 1; j < k; ++j) {
            int current_element;
            std::cin >> current_element;
            
            // 条件一检查：当前数组内部是否严格递增
            // 如果不是，就没希望了，喵呜...
            if (current_element <= prev_element) {
                is_possible = false;
            }
            
            all_elements.push_back(current_element);
            prev_element = current_element; // 更新前一个元素
        }
    }

    // 如果在读入时就发现某个子数组不满足递增，直接输出 NO
    if (!is_possible) {
        std::cout << "NO\n";
        return;
    }

    // 如果所有元素加起来是空的或者只有一个，那肯定是连续的呀！
    if (all_elements.size() <= 1) {
        std::cout << "YES\n";
        return;
    }
    
    // 条件二检查：全局的数字集合是否连续
    // 1. 排序
    std::sort(all_elements.begin(), all_elements.end());

    // 2. 检查相邻元素是否差值为 1
    for (size_t i = 1; i < all_elements.size(); ++i) {
        // 如果出现重复数字(差值为0)或者有间隔(差值>1)，就失败了
        if (all_elements[i] != all_elements[i-1] + 1) {
            std::cout << "NO\n";
            return;
        }
    }

    // 所有检查都通过了，太棒了！
    std::cout << "YES\n";
}

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

    solve();

    return 0;
}

复杂度分析

• 时间复杂度: $O(N \log N)$ 这里的 $N$ 是所有小数组中元素的总个数，的说。

  • 读入所有元素并检查每个小数组的内部顺序，这个过程需要遍历所有元素一次，所以是 $O(N)$。
  • 最耗时的部分是 std::sort，它对包含 $N$ 个元素的 vector 进行排序，时间复杂度是 $O(N \log N)$。
  • 最后遍历排序好的数组检查连续性，也是 $O(N)$。 所以总的时间复杂度由排序决定，就是 $O(N \log N)$ 啦。

• 空间复杂度: $O(N)$ 我们需要一个 std::vector 来存储所有 $N$ 个元素，所以占用的额外空间和总元素数量成正比，是 $O(N)$，喵~

知识点总结

这道题真有趣，它教会了我们一个重要的解题思想：分解问题！

一个看似复杂的“能否合并成连续数组”的问题，被我们分解成了两个简单又清晰的子问题：

1. 局部性质：每个子数组内部必须有序。
2. 全局性质：所有元素集合起来必须构成一个无重复、无间断的序列。

这个方法在很多算法题里都很有用哦！当你遇到一个大问题时，不妨像猫咪拆毛线球一样，先找到线头，把它分解成几个可以独立解决的小问题。

此外，这道题也巩固了排序算法的应用。排序是检查一组数是否具有特定性质（如唯一性、连续性）的强大工具。只要排好序，很多问题就变得一目了然了呢！

希望我的题解能帮助到你，加油哦，主人！喵~