自动搬运

查看原文

来自洛谷，原作者为

	yummy 这个人是时代的眼泪，什么也没有留下

搬运于2025-08-24 21:17:17，当前版本为作者最后更新于2025-01-21 13:16:39，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

本题为语法综合题，考查选手的二维数组、简单排序的知识，整体相对套路，因此较多选手反馈不如 G 题困难。

本题完全依照题意模拟即可。以下每条分割线表示一处小坑或难点。

本题把每一列同学作为一个整体，$n,m$ 谁是行谁是列容易弄混；$i,j$ 谁是行谁是列也容易弄混。

一种解决办法是规定 $i$ 表示第几行，$j$ 表示第几列，并从始至终采用同一套命名规则。

注意本题 $a_{i,j}\le 10^9$，尽管 $a_{i,j}$ 不会爆 int，但是计算每一列同学知识水平和（记为 s[j]）时，s[j] 会爆 int，要开 long long。

另外，对于每一次调整，我们计算 s[j] 时要记得清零，否则求出的总和会发生错误。

		long long mxv=0,mnv=1e18;
		for(int j=1;j<=m;j++){
			s[j]=0;
			for(int i=1;i<=n;i++)
				s[j]+=a[i][j];
			mxv=max(mxv,s[j]);
			mnv=min(mnv,s[j]);
		}

使用 cols[] 来记录有哪些列离开座位了，ccol 表示有几列离开座位了。此时，可以用 ccol*n+i 来计算 a[i][j] 这个同学在走廊上的原始下标。令 hall[i] 为走廊上第 $i$ 个同学，有如下代码：

		int ccol=0;
		for(int j=1;j<=m;j++){
			if(s[j]==mnv or s[j]==mxv){
				for(int i=1;i<=n;i++)
					hall[ccol*n+i]=a[i][j];
				ccol++;
				cols[ccol]=j;
			}
		}

排序时，如果大家只会从小到大排序而不会反过来，那么我们可以直接让 hall[1] 成为走廊上倒数第 $1$ 个同学。

蛇形排队时，一种写法是严格按照题意，对 i%2 进行讨论，另一种写法则是每次排完一行我就对 cols[] 数组翻转。这里采用前一种写法。

		int chall=ccol*n;
		for(int i=1;i<=chall;i++)
			for(int j=chall;j>i;j--)
				if(hall[j-1]>hall[j])
					swap(hall[j-1],hall[j]);
		for(int i=1;i<=n;i++){
			if(i%2){
				for(int j=1;j<=ccol;j++){
					a[i][cols[j]]=hall[chall];
					chall--;
				}
			}
			else{
				for(int j=ccol;j>0;j--){
					a[i][cols[j]]=hall[chall];
					chall--;
				}
			}
		}