题解 B4127：分队平衡

· · 题解

本题为语法综合题，考查选手的二维数组、简单排序的知识，整体相对套路，因此较多选手反馈不如 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--;
                }
            }
        }