自动搬运

查看原文

来自洛谷，原作者为

	AL8624 **

搬运于2025-08-24 22:45:31，当前版本为作者最后更新于2023-08-02 20:29:12，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

注意，如果你想要学习正解的话请略过本篇题解，本篇题解仅说明如何随机化乱搞过这道题

upd: 上传了代码

part 1 贪心

首先你可以想到一个显然假的贪心：从 $1 \sim n$ 考虑，对于每个转圈枚举出转多少对总答案的影响最小。

但是这个贪心有后效性，所以会得到错误的解。

part 2 随机化

你发现拼合多个错误的贪心和 dp 可以得到近似解。

你考虑这个错误的贪心算法的正确性和顺序有关 ，一个好的顺序可以瞬间帮你得到正确答案。

于是你考虑随机化这个序列，然后你发现随机 $300$ 次的时候 $1 \leq k \leq 3$ 能得到正解，但是 $k=4$ 的时候似乎会得到错误的解。

通过调参，可以发现随机 $600$ 次的时候 $k=4$ 可以得到正确的解，但是前面会被卡常，于是考虑数据点分治

然后喜提最劣解（10s）

如果 WA 了可以尝试改变随机数种子多交几发，应该是很稳定基本能过的

part 3 代码

可能有略微压行，见谅

#include<bits/stdc++.h>
using namespace std;
int n,T,k,a[200010][10];//为了随机化时连续访问所以把10开在后面
int mn[10],mx[10];
int main(){
	freopen("lock.in","r",stdin),freopen("lock.out","w",stdout);
	srand(1679057163);//此随机种子可以通过infoj的民间数据
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>T>>k;
	while(T--){
		cin>>n;
		for(int i(1);i<=k;++i)for(int j(1);j<=n;++j)cin>>a[j][i];
		int ans(1e9),en(k==4?600:300);//可以发现k=4的时候n比较小
		for (int i=1;i<=en;++i) {
			random_shuffle(a+1,a+n+1);
			memset(mx,-0x3f,sizeof(mx));
			memset(mn,0x3f,sizeof(mn));
			for(int j(1);j<=n;++j){
				int v(1e9),p;
				for(int x(0);x^k;++x) {
					int tmp(0);
					for(int y(1);y<=k;++y){
						const int Tmp=(y+x-1)%k+1;
						tmp=max(tmp,max(mx[y],a[j][Tmp])-min(mn[y],a[j][Tmp]));
					}
					v=tmp<v?(p=x,tmp):v;
				}
				for(int y=1;y<=k;++y) {
					const int Tmp=(y+p-1)%k+1;
					mx[y]=max(mx[y],a[j][Tmp]);
					mn[y]=min(mn[y],a[j][Tmp]);
				}
				if(ans<=v)break;//如果无法更新答案了就退出
			}
			int ret(0);
			for(int i=1;i<=k;++i)ret=max(ret,mx[i]-mn[i]);
			ans=min(ans,ret);
		}
		cout<<ans<<'\n';
	}
	return 0;