【GESP】C++四级真题 luogu-B4416 [GESP202509 四级] 最长连续段
GESP C++ 2025年9月四级真题，排序考点，难度⭐⭐★☆☆。
luogu-B4416 [GESP202509 四级] 最长连续段
题目要求
题目描述
对于 $k$ 个整数构成的数组 $[b_1, b_2, \ldots, b_k]$，如果对 $1 \leq i < k$ 都有 $b_{i+1} = b_i + 1$，那么称数组 $b$ 是一个连续段。
给定由 $n$ 个整数构成的数组 $[a_1, a_2, \ldots, a_n]$，你可以任意重排数组 $a$ 中元素顺序。请问在重排顺序之后，$a$ 所有是连续段的子数组中，最长的子数组长度是多少？
例如，对于数组 $[1, 0, 2, 4]$，可以将其重排为 $[4, 0, 1, 2]$，有以下 $10$ 个子数组：
\[[4], [0], [1], [2], [4, 0], [0, 1], [1, 2], [4, 0, 1], [0, 1, 2], [4, 0, 1, 2]\]其中除 $[4, 0], [4, 0, 1], [4, 0, 1, 2]$ 以外的子数组均是连续段，因此是连续段的子数组中，最长子数组长度为 3。
输入格式
第一行，一个正整数 $n$，表示数组长度。
第二行，$n$ 个整数 $a_1, a_2, \ldots, a_n$，表示数组中的整数。
输出格式
一行，一个整数，表示数组 $a$ 重排顺序后，所有是连续段的子数组的最长长度。
输入输出样例 #1
输入 #1
1
2
4
1 0 2 4
输出 #1
1
3
输入输出样例 #2
输入 #2
1
2
9
9 9 8 2 4 4 3 5 3
输出 #2
1
4
说明/提示
对于 $40\%$ 的测试点，保证 $1 \leq n \leq 8$。
对于所有测试点，保证 $1 \leq n \leq 10^5$，$-10^9 \leq a_i \leq 10^9$。
题目分析
核心思路
重排数组后，我们关心的是 “连续段” ——即子数组中相邻元素差严格为 1。
要让这样的段尽可能长，最直观的策略是：
- 把数组排序，这样相同的数会相邻，且数值单调不降；
- 从左到右扫描，把“差为 1”的相邻数连成一段；
- 重复数字对“连续段”长度无贡献，直接跳过；
- 每当遇到差不为 1 时，就结束当前段，更新答案并开启新段。
由于排序后所有“可能连续”的数都已相邻，上述贪心一定能找到全局最优。
复杂度
- 排序：$O(n \log n)$，$n \le 10^5$ 轻松通过；
- 扫描：$O(n)$。
边界注意
- 单元素也算连续段，初始
count = 1； - 最后一次段要在循环外再取一次
max。
示例代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <algorithm>
#include <iostream>
// 最大数据范围：1e5 + 5
const int MAX_N = 1 * 10e5 + 5;
int num_ary[MAX_N];
int main() {
int n;
std::cin >> n;
// 读入原始数组
for (int i = 0; i < n; i++) {
std::cin >> num_ary[i];
}
// 关键思路：排序后，相同数字会相邻，连续段只可能由“排序后相邻且差为 1”的数字组成
std::sort(num_ary, num_ary + n);
int max_count = 0; // 记录全局最长连续段长度
int count = 1; // 当前连续段长度，初始为 1（单个数字也算连续段）
int idx = 0; // 当前连续段的起始下标
for (int i = idx; i < n; i++) {
// 跳过重复数字：重复数字对“连续段”长度无贡献
if (num_ary[i + 1] == num_ary[i]) {
idx++;
continue;
}
// 若下一个数字刚好比当前大 1，则当前连续段可以延长
else if (num_ary[i + 1] == num_ary[i] + 1) {
count++;
idx++;
}
// 否则连续段中断，更新答案并重启计数
else {
max_count = std::max(max_count, count);
count = 1;
idx = i + 1;
}
}
// 最后一次连续段可能未被更新，再取一次最大值
max_count = std::max(max_count, count);
std::cout << max_count << std::endl;
return 0;
}
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
GESP 学习专题站：GESP WIKI
“luogu-”系列题目可在洛谷题库进行在线评测。
“bcqm-”系列题目可在编程启蒙题库进行在线评测。
欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答
欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总
欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助
