洛谷 B4416：[GESP202509 四级] 最长连续段 ← sort+unique

​【题目来源】
https://www.luogu.com.cn/problem/B4416

【题目描述】
对于 k 个整数构成的数组 [b1, b2, …, bk]，如果对 1≤i<k 都有 b_i+1=b_i+1，那么称数组 b 是一个连续段。
给定由 n 个整数构成的数组 [a1, a2, …, an]，你可以任意重排数组 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 个整数 a1, a2, …, an，表示数组中的整数。

【输出格式】
一行，一个整数，表示数组 a 重排顺序后，所有是连续段的子数组的最长长度。

【输入样例】
9
9 9 8 2 4 4 3 5 3​​​​​​​

【输出样例】
4

【数据范围】
对于 40% 的测试点，保证 1≤n≤8。
对于所有测试点，保证 1≤n≤10^5，−10^9≤ai≤10^9。​​​​​​​

【算法分析】
已知数组 a 中的元素下标从 0 开始，若要利用 STL unique 函数将数组 a 中的 n 个元素去重后升序输出，需要经过以下三步：
1. 利用 sort(a,a+n); 函数对数组 a 中的 n 个元素进行排序。
2. 利用 unique(a,a+n)-a; 计算数组 a 中不重复元素的个数。切记，STL unique 函数并没有将重复的元素删去，而是依序排在了不重复元素的后面。
3. 输出a[i]，i=1 ~ unique(a,a+n)-a。

【算法代码】

#include <bits/stdc++.h>
using namespace std;const int maxn=1e5+5;
int a[maxn];int main() {int n;cin>>n;for(int i=0; i<n; i++) {cin>>a[i];}sort(a,a+n);int len=unique(a,a+n)-a;int cnt=1,imx=1;for(int i=1; i<len; i++) {if(a[i]-a[i-1]==1) {cnt++;imx=max(imx,cnt);} else cnt=1;}cout<<imx<<endl;return 0;
}/*
in:
9
9 9 8 2 4 4 3 5 3out:
4
*/

【参考文献】
https://blog.csdn.net/guolianggsta/article/details/152925085
https://gesp.ccf.org.cn/101/attach/1703973044092960.pdf
https://blog.csdn.net/hnjzsyjyj/article/details/146331059
https://blog.csdn.net/hnjzsyjyj/article/details/153268411
https://blog.csdn.net/hnjzsyjyj/article/details/127197232