自动搬运

查看原文

来自洛谷，原作者为

	zhangzhihao2 一只卷毛狒狒

搬运于2025-08-24 21:14:20，当前版本为作者最后更新于2022-10-18 15:10:42，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

B3675 [语言月赛202210] 军训

Source & Knowledge

2022 年 10 月语言月赛，由洛谷网校入门计划/基础计划提供。

本题考察对数学知识和排序算法的应用。

文字题解

题目大意

给出两个 $n$ 行 $m$ 列的数字矩阵，计算出这两个矩阵每行 $m$ 个数字的方差，并将这两个矩阵中第 $i$ 行方差相加，得到第 $i$ 行的方差和。设计一个方案，通过对调某两行的位置若干次，使这 $n$ 行的方差和单调递增（即后面的数一定大于或等于前面的数）。

解析

如果知道如何计算方差，可以不用理解题目给出的计算公式。

本题的第一个难点在于如何理解计算一个矩阵 $a$ 中第 $i$ 行方差的公式：

$$\dfrac{1}{m} \times \sum\limits_{j=1}^{m}{\Bigg(a_{i,j}-\dfrac{\sum\limits_{k=1}^{m}{a_{i,k}}}{m}\Bigg)^2} $$

题目中已经给出解释：$\sum\limits_{j=1}^m{a_{i,j}}$ 代表 $a_{i,1}+a_{i,2}+a_{i,3}+\cdots+a_{i,m}$ 。$\sum$ 符号表示求和，可以读作“西格玛”。它下方的等式为：枚举的变量名 $=$ 枚举的初始值，上方的数字或字母表示枚举的上界，右边的单项式或带括号的多项式表示需要求和的内容。参考题目中的解释可以更加清晰地理解这些用法。

那么，可以知道 $\sum\limits_{k=1}^{m}{a_{i,k}}$ 代表 $a_{i,1}+a_{i,2}+a_{i,3}+\cdots+a_{i,m}$ ，也就是第 $i$ 行数字的总和。因此 $\dfrac{\sum\limits_{k=1}^{m}{a_{i,k}}}{m}$ 自然就是第 $i$ 行数字的平均值咯！

现在这个公式就更好理解了，设 $x_i$ 为第 $i$ 行数字的平均值，那么这个公式就变成了：

$$\dfrac{1}{m} \times \sum\limits_{j=1}^{m}{(a_{i,j}-x_i)^2} $$

$\sum\limits_{j=1}^m$ 的意思是从 $1$ 到 $m$ 枚举 $j$ 。所以这个公式的意思就是第 $i$ 行的每个数字与这一行平均值的差的平方之和，再除以 $m$。

那么矩阵 $b$ 每一行的计算方法也同理，只需将两个矩阵中第 $i$ 行的方差相加就能得到这行的方差和，第 $i$ 行的方差和记 $num_i$。

---

本题的第二个难点在于如何给出正确的交换位置的方案。

本题要求我们通过合理的交换来为这 $n$ 行的方差和进行排序，且操作次数必须小于 $n^2$ 。

这里给出两个解决方案（当然还有更多的）。其中一个就是冒泡排序。这也是比较好想的一个思路。如果没学过，可以看看我摘录的一段百度百科：

它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来。走访元素的工作是重复地进行，直到没有相邻元素需要交换，也就是说该元素列已经排序完成。

只需要正常地冒泡排序，在过程中用数组记录下每一次交换操作。时间复杂度 $O(n^2)$ ，交换次数在 $n^2$ 级别，但一定小于 $n^2$ 。

另一个是选择排序，每次比较得出未排序部分的最大值，将最大值所在位置与未排序部分的最后一个位置交换。注意，如果这两个位置为同一个，则无需交换。 时间复杂度 $O(n^2)$ ，但交换次数一定小于 $n$ ，比上一种方法更加优越。

因此完成本题需要分以下几个步骤：

1. 读入数据；
2. 计算两个矩阵每一行的平均值（这行的总和除以 $m$ ）；
3. 计算两个矩阵每一行的方差和；
4. 使用各种方法对方差和数组进行排序和操作记录（以上方法供参考）；
5. 将操作记录输出。

注意事项

• $n, m$ 的大小均可以达到 $1000$ ，开数组时要注意。
• 注意读入顺序，先读入 $m$ 再读入 $n$ 。
• 因为整型数据除以整型数据得到的商是向 0 取整的结果，因此在求平均数的过程中，需要使用强制类型转换，使得到的结果为浮点数。
• 平均数和方差和数组需要用浮点数类型存储。
• 由于矩阵 $n$ 行 $m$ 列，因此计算某一行平均值和方差和时需要循环 $m$ 次，而排序时 $for()$ 语句中只需要用到 $n$ ，注意不要混淆。

视频题解

完整代码见视频题解。