GESP题解 | 最长连续段

题目理解

这道题可以任意重排数组，然后找最长的连续段（子数组里每个数都比前一个大 1）。
因为能重排，所以最优策略一定是把数组从小到大排序，然后找最长的连续整数序列。

---

核心思路

1. 排序：把数组从小到大排好，连续的数字会挨在一起。
2. 遍历统计：
   • 如果当前数 = 前一个数 + 1 → 连续长度 +1
   • 如果当前数 = 前一个数 → 重复数字，不打断连续，长度不变
   • 如果数字不连续也不重复 → 连续长度重置为 1
3. 记录最大值：遍历过程中一直更新最长长度。

---

逐行代码精讲

#include<bits/stdc++.h>
using namespace std;

• 万能头文件，包含所有需要的库（排序、输入输出等）。

int n, a[100010];

• n：数组长度
• a[]：存数组的固定大小数组（不开 vector）
• 大小开 1e5+10 满足题目 $n \le 10^5$ 的要求。

int main() {
    cin >> n;

• 输入数组长度。

    for (int i = 1;i <= n;i++) {
        cin >> a[i];
    }

• 从 1 开始输入，数组下标从 1 开始用。

    sort (a + 1, a + n + 1);

• 对数组从 a[1] 到 a[n] 排序。
• 排序后连续数字挨在一起，方便找最长连续段。

    int x = 1;
    int y = 1;

• x：最终答案（最长连续段长度）
• y：当前正在统计的连续段长度
• 初始都是 1，因为单个数字本身就是长度为 1 的连续段。

    for (int i = 2;i <= n;i++) {

• 从第 2 个数开始遍历（要和前一个比较）。

        if (a[i] == a[i - 1] + 1) {
            y++;
            if (y > x) {
                x = y;
            }
        }

• 连续 +1：当前连续长度 +1
• 更新最长答案 x。

        else if (a[i] != a[i - 1]) {
            y = 1;
        }

• 不连续、不重复：连续中断，重置为 1
• 如果是重复数字，这里不执行，y 保持不变，不打断连续。

    }
    cout << x;
    return 0;
}

• 输出最长连续段长度，结束程序。

---

样例演算（超级清楚）

样例 1

输入：

4
1 0 2 4

排序后：0 1 2 4

遍历：

• i=2，a[2]=1 = 0+1 → y=2，x=2
• i=3，a[3]=2 = 1+1 → y=3，x=3
• i=4，a[4]=4 不连续 → y=1

最终输出：3

---

样例 2

输入：

9
9 9 8 2 4 4 3 5 3

排序后：2 3 3 4 4 5 8 9 9

遍历：

• 2→3 → y=2
• 3=3 → 不变
• 3→4 → y=3
• 4=4 → 不变
• 4→5 → y=4 （x=4）
• 5→8 中断 → 重置
• 后面不影响最大值

最终输出：4

---

为什么这代码是对的？

1. 重排 = 排序：想得到最长连续段，一定是排序后最优。
2. 重复数字不中断：题目允许重排，重复数字不破坏连续。
3. 线性遍历 O(n)：速度极快，能过 $10^5$ 大数据。