OneCoder Avatar
OneCodercoderli.com · 1024 篇博文
四级

C++ 算法考级专栏

🎨 视觉封面

【GESP】C++四级真题 luogu-B4416 [GESP202509 四级] 最长连续段

📅 2025-10-06·✍️ OneCoder·计算中...·⏱️ 6 分钟

GESP C++ 2025年9月四级真题,排序考点,难度⭐⭐★☆☆。

luogu-B4416 [GESP202509 四级] 最长连续段

题目要求

题目描述

对于 个整数构成的数组 ,如果对 都有 ,那么称数组 是一个连续段。

给定由 个整数构成的数组 ,你可以任意重排数组 中元素顺序。请问在重排顺序之后, 所有是连续段的子数组中,最长的子数组长度是多少?

例如,对于数组 ,可以将其重排为 ,有以下 个子数组:

其中除 以外的子数组均是连续段,因此是连续段的子数组中,最长子数组长度为 3。

输入格式

第一行,一个正整数 ,表示数组长度。

第二行, 个整数 ,表示数组中的整数。

输出格式

一行,一个整数,表示数组 重排顺序后,所有是连续段的子数组的最长长度。

输入输出样例 #1

输入 #1
PLAINTEXT2 行
4
1 0 2 4
输出 #1
PLAINTEXT1 行
3

输入输出样例 #2

输入 #2
PLAINTEXT2 行
9
9 9 8 2 4 4 3 5 3
输出 #2
PLAINTEXT1 行
4

说明/提示

对于 的测试点,保证 。

对于所有测试点,保证 ,。


题目分析

核心思路

重排数组后,我们关心的是 “连续段” ——即子数组中相邻元素差严格为 1。
要让这样的段尽可能长,最直观的策略是:

  1. 把数组排序,这样相同的数会相邻,且数值单调不降;
  2. 从左到右扫描,把“差为 1”的相邻数连成一段;
  3. 重复数字对“连续段”长度无贡献,直接跳过;
  4. 每当遇到差不为 1 时,就结束当前段,更新答案并开启新段。

由于排序后所有“可能连续”的数都已相邻,上述贪心一定能找到全局最优。

复杂度

  • 排序:, 轻松通过;
  • 扫描:。

边界注意

  • 单元素也算连续段,初始 count = 1;
  • 最后一次段要在循环外再取一次 max。

示例代码

C++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;
}

看完题解去实战!OneCoder C++ 信奥远征闯关平台 (oi.coderli.com)
💡 OneCoder 资源指引

所有代码开源上传至 GitHub:yummy-code 仓库 · GESP 专题站:GESP WIKI

🤝 技术交流与答疑

欢迎加入:C++ GESP/CSP 考级答疑群(688906745) 与 Java/Python交流群(982860385),点击可直接加群。

📚

猜你想读 · 相关文章推荐

OneCoder

OneCoder

一个中年人的自留地,记录学习 C++、GESP/NOI、Java、Python 与算法架构的心得体会。本站唯一网址:coderli.com

读者讨论与留言

共 0 条讨论
邮箱必填 · 支持 Markdown 格式与直接回复
💬 还没有读者留言,快来成为第一个讨论者吧!