B4416 [GESP202509 四级] 最长连续段

chen_zhe · 2025-11-24 11:56:24 · 题解

欢迎报名洛谷网校，报名课程可以获得对应组别的知识点讲解与答疑服务，期待和大家一起进步！点击图片即可报名。

:::align{center} :::

本题在 GESP 4 级范围内可能超纲，需要用到 GESP 5 级的分治算法（归并排序、快速排序）。

这道题目的核心在于理解“任意重排”这个条件。既然我们可以随意改变数组中元素的顺序，那么元素原本在什么位置就不重要了。题目实际上是在问：在这个数组的所有数字中，我们最多能挑出多少个数字，让它们组成一个连续递增的序列（例如 3, 4, 5, 6\dots ）？

为了找到最长的连续递增序列，最直观的方法就是先把手里的数字排好序。我们将输入的 n 个整数从小到大进行排序。排序后，如果存在连续的数字，它们一定会紧挨在一起。

我们遍历排序后的数组。在遍历过程中，我们需要关注当前数字和前一个数字的关系：

• 如果是重复数字，这对我们构成更长的连续序列没有帮助，直接跳过即可。
• 如果是连续数字，说明当前的连续序列断开没有断开，长度加 1。
• 如果不连续且不重复，说明之前的连续序列断掉了，我们需要重新开始计数，将当前长度重置为 1。

由于本题的数据范围为 1 \leq n \leq 10^5，且值域范围为 -10^9 \leq a_i \leq 10^9，因此无法使用 GESP 四级大纲中的【冒泡排序、插入排序、选择排序】完成本题。对于 C++ 和 Python 语言的选手，是自带排序库函数的。对于 C++，可以使用 sort 函数（引入头文件：algorithm），注意 sort 函数并非是纯粹的快速排序。

参考代码：

// 对数组 a 进行从小到大排序。
for (int i = 2; i <= n; ++i) {
    if (a[i] == a[i-1])
        ________; // 如果是重复数字
    if (a[i] == a[i-1] + 1)
        ________; // 如果是连续数字
    else 
        ________; // 之前的连续序列断掉了
    ________; // 更新当前记录到的最长长度
}