你说的对，我使用基数排序，脑子都不用动一下。

详见 Luogu P4604 [WC2017] 挑战。

排序操作的时间复杂度是线性的。

#include<bits/stdc++.h>
using namespace std;
using ui=unsigned int;
istream& fin=cin;
ostream& fout=cout;
template <typename ForwardIterator,
          typename = is_unsigned<typename ForwardIterator::value_type>>
void radixSort(ForwardIterator first, ForwardIterator last) {
  constexpr ui P = 8;
  constexpr size_t T = 4;
  size_t n = distance(first, last);
  ui W = 0;
  auto *dat = new typename ForwardIterator::value_type[n];
  for (size_t i = 0; i < T; ++i, W += P) {
    array<size_t, 1u << P> cnt{};
    for_each(first, last, [&](typename ForwardIterator::reference const x) {
      ++cnt[(x >> W) & ((1u << P) - 1)];
    });
    partial_sum(cnt.begin(), cnt.end(), cnt.begin());
    rotate(cnt.begin(), prev(cnt.end()), cnt.end()), cnt[0] = 0;
    for_each(first, last, [&](typename ForwardIterator::reference const x) {
      dat[cnt[(x >> W) & ((1u << P) - 1)]++] = x;
    });
    copy(dat, dat + n, first);
  }
  delete[] dat;
}
int main(void){
    ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
    size_t n;fin>>n;
    vector<ui> a(n);
    for (ui& i:a) fin>>i;
    radixSort(a.begin(),a.end());
    a.erase(unique(a.begin(),a.end()),a.end());
    ui ans=0,c=1;
    for (auto it=next(a.begin());it!=a.end();++it)
        if (*it-*prev(it)==1) ++c;
        else{
            ans=max(ans,c);
            c=1;
        }
    ans=max(ans,c);
    fout<<ans;
    return 0;
}

30 pts

$N < 10^3 , H_i<10^3$

直接使用 sort 快速排序

60 pts

$N < 10^7, H_i<10^7$

法一：桶排序(赛时打的)

int n,x,maxf,ans=1,maxc;

bool f[10000007];

int main(){
	n=read();
	for (int i=1;i<=n;i++){
		x=read();
		f[x]=1;
		maxf=max(maxf, x);
	}
	for (int i=1;i<=maxf;i++){
		if (f[i] && f[i-1]){
			ans++;
			maxc=max(maxc,ans);
		}
		else ans=1;
	}
	printf("%d",maxc);
	return 0;
}

法二：标记法

一个数可能会出现很多次，用一个 $vis_i$ 标记。 当这一个数第一次出现的时候，给自己打上标记，然后往两边去找以前打过标记的点，记录长度。

100 pts ： hash优化标记法

$N < 10^7, H_i<10^9$

$H_i$ 太大了，可以用散列hash

hash的代码实现：

struct hash_edge{//链表 （和链式前向星差不多）
	int x,nxt;
}e[10000007];
int head[10000007],tot;
void add_hash(int x){//加入
	int u=(x%9114514)+1;//恶臭的hash函数
	e[++tot]=(hash_edge){x,head[u]};
	head[u]=tot;
}
bool find_hash(int x){//查找
	for (int i=head[(x%9114514)+1];i;i=e[i].nxt){
		if (e[i].x==x)
			return 1;
	}
	return 0;
}

结合上一个方法，AC代码：

#include<iostream>
#include<cstdio>

using namespace std;

inline int read(){
	int x=0; char c=getchar();
	while (c<'0'||c>'9'){
		c=getchar();
	}
	while (c>='0'&&c<='9'){
		x=(x<<1)+(x<<3)+c-'0';
		c=getchar();
	}
	return x;
}

struct hash_edge{
	int x,nxt;
}e[10000007];
int head[10000007],tot;
void add_hash(int x){
	int u=(x%9114514)+1;
	e[++tot]=(hash_edge){x,head[u]};
	head[u]=tot;
}
bool find_hash(int x){
	for (int i=head[(x%9114514)+1];i;i=e[i].nxt){
		if (e[i].x==x)
			return 1;
	}
	return 0;
}

int n,x,maxn;

int main(){
	n=read();
	for (int i=1;i<=n;i++){
		x=read();
		if (!find_hash(x)){
			add_hash(x);
			int l=x,r=x;
			while (find_hash(r+1)) r++;
			while (find_hash(l-1)) l--;
			maxn=max(maxn,r-l+1);
		}
	}
	printf("%d",maxn);
	return 0;
} 

upd: 这个做法在随机数据下是优的，但是在可以造的递增的数据下跑的很慢，退化到 $O(n^2)$，不过wahning数据太水了。

我们发现1e7的数据和1e9的值域且必须每一个数都被枚举到，那么我们考虑bitset记录与线性做法

首先我们考虑，每种数只能让它被枚举到一次，否则多余枚举

我们设 $S_{i,j}$ 表示一个数 $h_i$ 除以 $1000000$ 的商和余数，然后用一个数组 $T_{i,j}$ 记录这个数是否被枚举过

然后统计答案

//	op=reads();
	while(op--){
		clr();
		n=reads();
		for(int i=1;i<=n;i++){
			h[i]=reads();
			S[h[i]/B][h[i]%B]=1;
		}
		for(int i=1;i<=n;i++){
			if(!T[h[i]/B][h[i]%B]){
				int l=h[i]-1,r=h[i]+1;
				while(r<=B&&S[r/B][r%B]) T[r/B][r%B]=1,r++;
				r--;
				while(l>=0&&S[l/B][l%B]) T[l/B][l%B]=1,l--;
				l++;
				ans=max(ans,r-l+1);
			}
		}
		printf("%d\n",ans);
	}

思路

对于一个数x，向前（<x）枚举最左到哪里，向后（>x）枚举最右能到哪里，答案为max（r-l+1）。

由于值域1e9太大会爆空间，考虑怎样存储

哈希+bitset

设模数为M，因为M<1e9，所以会有冲突（那就开二维呗）。定义bitset <N> a[100];。对于存储数x，即为a[x/N][x%N] = 1;。（这里N我取的是1e7，取其他的也可以）

code

#include <bits/stdc++.h>
using namespace std;
#define ll long long

namespace syr
{
	const ll N = 1e7;
	ll n, x, l, r, ans;
	bitset <N> a[100];
	void work()
	{
		cin>>n;
		for (ll i=1; i<=n; i++) {
			cin>>x;
			if (a[x/N][x%N]) continue;
			a[x/N][x%N] = 1;
			l = r = x;
			while (l>=0 && a[l/N][l%N]) l--;
			while (a[r/N][r%N]) r++;
			ans = max(ans, r-l-1);
		}
		cout<<ans<<'\n';
	}
}

int main()
{
	cin.tie(0)->sync_with_stdio(0);
	syr::work();
	return 0;
}