用乱搞做法,但是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;
}