逆天
查看原帖
逆天
817925
whileAK楼主2024/9/29 15:29

用乱搞做法,但是T了#5,10,17,18,19,在学校OJ上交了一发就过了,现在怀疑是洛谷评测环境不同导致的。有大神解释一下吗?

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void rd(int &p){
	p=0;int f(0);char z=getchar();
	while(z>'9'||z<'0'){if(z=='-')f^=1;z=getchar();}
	while(z>='0'&&z<='9')p=(p<<1)+(p<<3)+z-'0',z=getchar();
	if(f)p=-p;
}
void rdl(ll &p){
	p=0;int f(0);char z=getchar();
	while(z>'9'||z<'0'){if(z=='-')f^=1;z=getchar();}
	while(z>='0'&&z<='9')p=(p<<1)+(p<<3)+z-'0',z=getchar();
	if(f)p=-p;
}
const int N=5e4+50;
int t,k,n,a[5][N],id[N],mx[5],mn[5];
int solve(){
	int ans(1e9);
	for(int i(1);i<=k;++i)mn[i]=1e9,mx[i]=0;
	for(int I(1),i,x,y,z;I<=n;++I){
		z=1e9;i=id[I];
		for(int j(0);j<k;++j){
			x=a[1][i];
			for(int u(1);u<k;++u)a[u][i]=a[u+1][i];
			a[k][i]=x;x=0;
			for(int u(1);u<=k;++u){
				x=max(x,max(mx[u],a[u][i])-min(mn[u],a[u][i]));
			}
			if(z>x)z=x,y=j;
		}ans=z;
		for(int j(0);j<=y;++j){
			x=a[1][i];
			for(int u(1);u<k;++u)a[u][i]=a[u+1][i];
			a[k][i]=x;
		}
		for(int j(1);j<=k;++j)mx[j]=max(mx[j],a[j][i]),mn[j]=min(mn[j],a[j][i]);
	}return ans;
}
int main(){
	rd(t);rd(k);
	srand(time(0));
	for(int T(1);T<=t;++T){
		rd(n);
		for(int i(1);i<=k;++i){
			for(int j(1);j<=n;++j)rd(a[i][j]);
		}int ans(1e9),K;
		if(k==4)K=30000;
		else K=150000;
		for(int i(1);i<=n;++i)id[i]=i;
		long double bg=clock();
		while((clock()-bg)/CLOCKS_PER_SEC<=2.4/K*n){
			random_shuffle(id+1,id+n+1);
			ans=min(ans,solve());
		}
		printf("%d\n",ans);
	}
	return 0;
}
2024/9/29 15:29
加载中...