B3675 [语言月赛202210] 军训
zhangzhihao2
·
·
题解
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}
那么矩阵 $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$ ，注意不要混淆。
## 视频题解
完整代码见视频题解。
