【调出必关】邻接表做法RE60求条

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5;
int a[N];
int h[2*N],e[2*N],ne[2*N];
bool st[2*N];
int idx,o=N;

void ad(int u,int l){
    st[idx]=1;
    e[idx]=l+1;
    ne[idx]=h[u+o];
    h[u+o]=idx++;
}

void sol(int u)
{
    int p=u+o,q=(u-1)+o;
    if(h[q]==-1)ad(u,0);
    else
	{
        int mn=1e9,tp=-1;
        for(int i=h[q];i!=-1;i=ne[i])
		{
            if(st[i]&&e[i]<mn)
			{
                mn=e[i];
                tp=i;
            }
        }
        if(tp==-1)ad(u,0);
        else{
            st[tp]=0;
            ad(u,mn);
        }
    }
}

signed main(){
    int n;
    cin>>n;
    memset(h,-1,sizeof h);
    for(int i=1;i<=n;i++)
		cin>>a[i];
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++)
		sol(a[i]);
    int ans=1e9;
    for(int i=1;i<=n;i++)
	{
        int p=a[i]+o;
        for(int j=h[p];j!=-1;j=ne[j])
		{
            if(st[j])ans=min(ans,e[j]);
        }
    }
    cout<<ans;
    return 0;
}