202509-最长连续段(luogu-B4416)

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

4
1 0 2 4

输出 #1

3

输入输出样例 #2

输入 #2

9
9 9 8 2 4 4 3 5 3

输出 #2

4

说明/提示

对于 $40\%$ 的测试点，保证 $1 \leq n \leq 8$。

对于所有测试点，保证 $1 \leq n \leq 10^5$，$-10^9 \leq a_i \leq 10^9$。

题目分析

核心思路

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

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

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

复杂度

• 排序：$O(n \log n)$，$n \le 10^5$ 轻松通过；
• 扫描：$O(n)$。

边界注意

• 单元素也算连续段，初始 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;
}

本文由coderli.com原创，按照CC BY-NC-SA 4.0 进行授权

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

“luogu-”系列题目可在 洛谷题库 在线评测。

“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP 认证学习微信公众号