G4020 [GESP202509 四级] 最长连续段 题解

知识点：排序、去重、连续序列。

解题思路

用有序集合去重排序，顺次扫描；当前值等于前值+1则连续长度增加，否则从1重新开始。

为什么正确

排序后所有相邻整数必连续出现，重复值移除后不会干扰长度，逐段统计得到最长连续整数段。

易错点

重复数不能增加段长，也不应切断序列；数值与前值用long long。

复杂度

时间O(n log n)，空间O(n)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    set<long long>s;
    while(n--) {
        long long x;
        cin>>x;
        s.insert(x);
    }
    int ans=0,c=0;
    long long prev=-(1LL<<60);
    for(long long x:s) {
        c=x==prev+1?c+1:1;
        ans=max(ans,c);
        prev=x;
    }
    cout<<ans;
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用8个自行生成的测试点。