随机化数组的方法

来源于Problem - B - Codeforces (Unofficial mirror site, accelerated for Chinese users)

当时用随机化数组的方法过了，记录一下，以后可能用到

#include<bits/stdc++.h>
using namespace std;
struct tnode{
	int a[5];
}e[500050];
int zhan[10010],tot,zhan1[100010],cnt,bj[100010],nb[100010],nex[100010];
int cmp(int x,int y)
{
	int ans=0;
	for(int i=0;i<5;i++)
	if(e[x].a[i]<e[y].a[i])ans++;
	if(ans>=3)return true;
	else return false;
}
int main()
{
	srand((int)time(0));
//	freopen("std.in","r",stdin);
	int t;
	cin>>t;
	while(t--)
	{
		tot=0;cnt=0;
		int n;
		cin>>n;
		for(int i=1;i<=n;i++)
		{
			scanf("%d%d%d%d%d",&e[i].a[0],&e[i].a[1],&e[i].a[2],&e[i].a[3],&e[i].a[4]);
			bj[i]=0;
			nb[i]=0;
			nex[i]=i+1;
		}
		nex[n]=1;
		if(n==1)
		{
			cout<<1<<"\n";continue;
		}
		for(int t=1;t<=n;t++)
		{
			int maxn=1ll*rand()*rand()%n+1;
			while(nb[maxn]==1)
			{
//				int to=nex[maxn];
//				nex[maxn]=nex[to];
				maxn=nex[maxn];
			}
			nb[maxn]=1;
			if(!bj[maxn])
			for(int i=1;i<=n;i++)
			if(i!=maxn){
				if(cmp(maxn,i))
				{
					if(bj[i]!=1)
					{
						bj[i]=1;nb[i]=1;t++;
					}
				}
				else bj[maxn]=1;
			}
			if(t==n)break;
			for(int l=1,r;l<=n;l=r+1)
			{
				while(nb[l]!=0&&l<=n)l++;
				if(l>n)break;
				r=l;
				while(nb[r]==1&&r<=n)r++;
				if(r>n)
				{
					for(int j=l;j<=r;j++)
					nex[j]=nex[1];
				}else
				for(int j=l;j<=r;j++)
				nex[j]=nex[r];
			}
		}
		int maxn=-1;
		for(int i=1;i<=n;i++)
		if(!bj[i])maxn=i;
		cout<<maxn<<"\n";
//		for(int i=0;i<5;i++)
//		{
//			int bj=0,maxn=50100;
//			for(int j=1;j<=n;j++)
//			{
//				if(maxn>e[j].a[i])
//				{
//					bj=j;maxn=e[j].a[i];
//				}
//			}
//			zhan[++tot]=bj;
//		}
//		sort(zhan+1,zhan+tot+1);
//		tot=unique(zhan+1,zhan+tot+1)-zhan-1;
////		for(int i=1;i<=tot;i++)
////		cout<<zhan[i]<<" ";
////		cout<<"\n";
//		if(tot==1)
//		{
//			cout<<zhan[tot]<<"\n";continue;
//		}
//		int ans=0;
//		for(int i=1;i<=tot;i++)
//		{
//			int bj=0;
//			for(int j=1;j<=tot;j++)
//			if(j!=i){
//				if(!cmp(zhan[i],zhan[j]))bj=1;
//			}
//			if(!bj)
//			{
//				ans=1;
//				cout<<zhan[i]<<"\n";break;
//			}
//		}
//		if(!ans)
//		cout<<"-1"<<"\n";
	}
	return 0;
}