B4416 [GESP202509 四级] 最长连续段

欢迎报名洛谷网校，期待和大家一起进步！

本题在 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 函数并非是纯粹的快速排序。

参考代码：

CPP

sort(a + 1, a + n + 1);
int ans = 1;
int len = 1;
for (int i = 2; i <= n; ++i) {
    if (a[i] == a[i-1])
        continue;
    if (a[i] == a[i-1] + 1)
        len++;
    else 
        len = 1;
    if (len > ans)
        ans = len;
}

B4416 [GESP202509 四级] 最长连续段

文章操作

相关推荐

评论

B4416 [GESP202509 四级] 最长连续段