B4361 [GESP202506 四级] 排序

chen_zhe · 2025-07-27 12:04:58 · 题解

欢迎报名洛谷网校，报名课程可以获得对应组别的知识点讲解与答疑服务，期待和大家一起进步！点击图片即可报名。

:::align{center} :::

我们可以使用两层循环来检查队伍中任意两位同学的组合。外层循环从前往后遍历队伍中的每一位同学（比如第 i 位），内层循环则遍历排在他后面的所有同学（比如第 j 位，其中 j > i）。

对于每一对被选中的同学（第 i 位和第 j 位），我们都根据题目给出的排序规则来判断他们当前的位置是否“正确”。排序规则是：身高更高者优先，身高相同则体重更重者优先。那么，如果第 j 位同学的排序优先级比第 i 位同学更高（即第 j 位同学身高更高，或者身高相同但体重更重），这就意味着第 i 位同学“站错”了位置，他本应该在第 j 位同学的后面。

为了方便地存储每位同学的身高和体重，我们可以使用结构体（struct）存储学生信息：

struct Stu {
    int h, w;
    // h 代表身高，w 代表体重。
};

这样，上文所述的排序规则可以写作：

for (int i = 1; i < n; ++i) {
    for (int j = i + 1; j <= n; ++j) {
        // 情况一：p[j] 的身高比 p[i] 高
        bool c1 = ________;            
        // 情况二：两人身高相同，但 p[j] 的体重比 p[i] 重
        bool c2 = ________;
        // 只要任意一种情况成立，则需要交换
        ________
    }
}

这样做，我们只需要使用二重循环完成本题，时间复杂度为 O(n^2)，足以通过本题。在 GESP 5 级中，我们将进一步学习分治算法和归并排序，可以使用分治法将求解本题的答案的时间复杂度优化为 O(n \log n)。