怎么卡掉基数排序

题目

优秀的错解

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
char *p1,*p2,buf[10010];
inline void chmax(int&a,const int b){if(a<b)a=b;}
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,10000,stdin),p1==p2)?EOF:*p1++)
inline int read(){
	register int x=0;
	register char c=gc();
	while(c<48)c=gc();
	while(c>47)x=(x<<3)+(x<<1)+(c^48),c=gc();
	return x;
}
int a[200010];
static const int n=read();
inline void radix_sort(){
    static int cnt[256],t[200010];
    int*x=a,*y=t;
    for(register int d=0;d<4;++d){
    	memset(cnt,0,1024);
        for(register int i=0;i<n;++i)++cnt[x[i]>>(d<<3)&255];
        for(register int i=1;i<256;++i)cnt[i]+=cnt[i-1];
        for(register int i=n-1;~i;--i)y[--cnt[x[i]>>(d<<3)&255]]=x[i];
        swap(x,y);
    }
    for(register int i=0;i<n;++i)a[i]=x[i];
}
int main(){
    int ans=0;
    for(register int i=0;i<n;++i)a[i]=read();
    radix_sort();
    for(register int i=1;i<n;++i)chmax(ans,a[i]-a[i-1]);
    printf("%d",ans);
    return 0;
}

劣质的正解

#include<cstdio>
inline int iread(){char c;int x=0,y=1;c=getchar();while(c<'0'||c>'9'){if(c=='-') y=-1;c=getchar();}while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^'0');c=getchar();}return x*y;}
int n,a[200005];
struct node{
	int xmin=-1,dmax=0;
}t[200005];
int q,i,p;
int num;
int main(){
	n=iread();
	for(i=1;i<=n;++i) a[i]=iread();
	q=p=a[1];
	for(int i=2;i<=n;++i){
		if(q<a[i]) q=a[i];
		if(p>a[i]) p=a[i];
	}
	q-=p;
	if(!q){
		puts("0");
		return 0;
	}
	if(q==1){
		puts("1");
		return 0;
	}
	for(i=1;i<=n;++i){
		num=((a[i]-p)*1ll*(n-1)/q);
		++num;
		if(t[num].xmin==-1||t[num].xmin>a[i]){
			t[num].xmin=a[i];
		}
		if(t[num].dmax==0||t[num].dmax<a[i]){
			t[num].dmax=a[i];
		}
	}
	p=t[1].dmax;
	q=0;
	for(i=2;i<=n;++i){
		if(t[i].xmin!=-1){
			if(t[i].xmin-p>q){
				q=t[i].xmin-p;
			}
			p=t[i].dmax;
		}
	}
	printf("%d",q);
	return 0;
}