C++ 算法考级专栏
🎨 视觉封面【GESP】C++四级真题 luogu-B4416 [GESP202509 四级] 最长连续段
GESP C++ 2025年9月四级真题,排序考点,难度⭐⭐★☆☆。
luogu-B4416 [GESP202509 四级] 最长连续段
题目要求
题目描述
对于 个整数构成的数组 ,如果对 都有 ,那么称数组 是一个连续段。
给定由 个整数构成的数组 ,你可以任意重排数组 中元素顺序。请问在重排顺序之后, 所有是连续段的子数组中,最长的子数组长度是多少?
例如,对于数组 ,可以将其重排为 ,有以下 个子数组:
其中除 以外的子数组均是连续段,因此是连续段的子数组中,最长子数组长度为 3。
输入格式
第一行,一个正整数 ,表示数组长度。
第二行, 个整数 ,表示数组中的整数。
输出格式
一行,一个整数,表示数组 重排顺序后,所有是连续段的子数组的最长长度。
输入输出样例 #1
输入 #1
4
1 0 2 4输出 #1
3输入输出样例 #2
输入 #2
9
9 9 8 2 4 4 3 5 3输出 #2
4说明/提示
对于 的测试点,保证 。
对于所有测试点,保证 ,。
题目分析
核心思路
重排数组后,我们关心的是 “连续段” ——即子数组中相邻元素差严格为 1。
要让这样的段尽可能长,最直观的策略是:
- 把数组排序,这样相同的数会相邻,且数值单调不降;
- 从左到右扫描,把“差为 1”的相邻数连成一段;
- 重复数字对“连续段”长度无贡献,直接跳过;
- 每当遇到差不为 1 时,就结束当前段,更新答案并开启新段。
由于排序后所有“可能连续”的数都已相邻,上述贪心一定能找到全局最优。
复杂度
- 排序:, 轻松通过;
- 扫描:。
边界注意
- 单元素也算连续段,初始
count = 1; - 最后一次段要在循环外再取一次
max。
示例代码
#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:yummy-code 仓库 · GESP 专题站:GESP WIKI
欢迎加入:C++ GESP/CSP 考级答疑群(688906745) 与 Java/Python交流群(982860385),点击可直接加群。
猜你想读 · 相关文章推荐
【GESP】C++四级真题 luogu-B3851 [GESP202306 四级] 图像压缩
GESP C++四级真题,函数、结构体、多维数组等应用练习,难度⭐⭐⭐☆☆。个人认为23年GESP考试设立初期各级考试的题难度都不小,本题应该是四级真题中难度较大的一个。在洛谷也是评定为普及/提高。
【GESP】C++四级真题 luogu-B3928 [GESP202312 四级] 田忌赛马
GESP C++四级2023年12月真题。本题为一维数组和排序的应用练习,难度⭐⭐★☆☆。本题在洛谷评定为普及-。 本质上说,这里的算法策略采用的是贪心策略,属于GESP五级的内容,但是作为四级考生,在忽略所谓对贪心策略理解的情况下,也可以通过自己的思考解决。
【GESP】C++四级真题 luogu-B3959 [GESP202403 四级] 做题
GESP C++四级2024年3月真题。本题主要考察排序操作。难度不大⭐⭐★☆☆。本题在洛谷评定为普及-。
OneCoder
一个中年人的自留地,记录学习 C++、GESP/NOI、Java、Python 与算法架构的心得体会。本站唯一网址:coderli.com

