P2521. 比赛的冠亚季军

解题思路

总体思路

数据量只有 10000，并不是一个很大的数据量，可以直接根据题意对比赛进行模拟。由于每一轮比赛都会使得总人数减半，大概需要 logN 轮比赛，每轮比赛考虑的人数和 N 相关，所以总的时间复杂度为 O(NlogN)。

比赛过程模拟

在剩余人数大于等于 5 的时候，比赛的逻辑是类似的。当：

• 剩余人数 len(nums) 为偶数，则编号相邻的人进行比拼，实力更高的人进入下一轮
• 剩余人数 len(nums) 为奇数，除了相邻的人需要进行比拼之外，编号最末尾的人轮空进入下一轮

故可以用以下代码来表示这个比赛过程：

在每一次 while 循环中，使用了一个新的数组 nums_new 来储存当前数组 nums 中进入下一轮的选手情况。并且在本次 while 循环结束后，我们将 nums_new 拷贝给了 nums，用作下一次 while 循环操作。

决胜轮次处理

比赛进行到最后的决胜轮次只会有两种情况：剩下 3 个人或者 4 个人。

剩下 3 个人

假设这三个人按照 id 大小排序分别为 A B C：

• A 和 B 进行比赛，胜者为冠军，败者为亚军
• C 轮空，直接成为季军

对应代码如下：

剩下 4 个人

假设这三个人按照 id 大小排序分别为 A B C D。这就是示例所给出的情况：

• A 和 B 进行比赛，C 和 D 进行比赛
• 上述比赛中的两个胜者进行冠军争夺战，胜者为冠军，败者为亚军
• 上述比赛中的两个败者进行季军争夺战，胜者为季军

对应代码如下：

补充说明

PS：本题的题目描述非常模糊，有不少同学提出异议。对于最后决胜轮次的比拼规则，只能按照唯一的示例进行猜测。

如果关于最后剩余人数为 3 的情况的冠亚季军角逐的比赛顺序为：先进行 A 跟 B 的比拼，败者为季军，其中胜者再跟轮空的 C 进行比拼决出冠亚军。那么对应的代码则修改为：

要学会能够自己根据不同的模糊题意描述进行代码的修改和测试。