【模拟】比赛的冠亚季军（许老师题解）
【模拟】比赛的冠亚季军（许老师题解）
题目描述与示例
本题练习地址：https://www.algomooc.com/problem/P2521
题目描述
有N (3 <= N < 10000)个运动员，他们的id为0到N-1,他们的实力由一组整数表示。他们之间进行比赛，需要决出冠亚军。比赛的规则是0号和1号比赛，2号和3号比赛，以此类推，每一轮，相邻的运动员进行比赛，获胜的进入下一轮，实力值大的获胜，实力值相等的情况，id小的情况下获胜；轮空的直接进入下一轮。
输入描述
输入一行N个数字代表N个运动员的实力值(0 <= 实力值 <= 10000000000).
输出描述
输出冠亚季军的id，用空格隔开
示例
输入
2 3 4 5输出
3 1 2说明
第一轮比赛id为0实力值为2的运动员和id为1实力值为3的运动员比赛，1号胜出进入下一轮争夺冠亚军。id为2实力值为4的运动员和id为3实力值为5的运动员比赛，3号胜出进入下一轮争夺冠亚军。
冠亚军比赛，3号胜1号故冠军为3号，亚军为1号。
2号与0号，比赛进行季军的争夺，2号实力值为4，0号实力值2，故2号胜出，得季军。
冠亚季军为3 1 2
解题思路
数据量只有10000，并不是一个很大的数据量，可以直接根据题意对比赛进行模拟。由于每一轮比赛都会使得总人数减半，大概需要logN轮比赛，每轮比赛考虑的人数和N相关，所以总的时间复杂度为O(NlogN)。
在剩余人数大于等于5的时候，比赛的逻辑是类似的。当
- 剩余人数
len(nums)为偶数，则编号相邻的人进行比拼，实力更高的人进入下一轮 - 剩余人数
len(nums)为奇数，除了相邻的人需要进行比拼之外，编号最末尾的人轮空进入下一轮
故可以用以下代码来表示这个比赛过程
# 输入
nums = list(map(int, input().split()))
# 同时储存实力num和原编号i
nums = [(num, idx) for idx, num in enumerate(nums)]
# 进行若干次循环，退出循环的条件是nums的长度小于5
# 经过若干轮比拼之后，nums的最终长度会是3或4
while len(nums) >= 5:
# 构建一个空列表，用于储存该轮比赛的结果
nums_new = list()
# 遍历当前的nums数组，注意步长取2，表示每次取相邻的两个人进行比赛
# 前一个人为nums[i]，后一个人为nums[i+1]
for i in range(0, len(nums)-1, 2):
# 如果比赛之后，前一个人的实力大于等于后一个的实力
# 则将前一个人的情况加入nums_new中
# 注意：这里之所以是≥，是因为题目要求当两个人实力相等时，认为是id小的获胜
if nums[i][0] >= nums[i+1][0]:
nums_new.append(nums[i])
# 否则将后一个人的情况加入nums_new中
else:
nums_new.append(nums[i+1])
# 如果nums的长度是奇数，说明最后一个人轮空，必须加入下一轮
if len(nums) % 2 == 1:
nums_new.append(nums[-1])
# 最后，重置nums为nums_new，用于下一个循环操作
nums = nums_new在每一次while循环中，使用了一个新的数组nums_new来储存当前数组nums中进入下一轮的选手情况。
并且在本次while循环结束后，我们将nums_new拷贝给了nums，用作下一次while循环操作。
比赛进行到最后的决胜轮次只会有两种情况，剩下3个人或者4个人。若
- 剩下
3个人，假设这三个人按照id大小排序分别为A B CA和B进行比赛，胜者为冠军，败者为亚军C轮空，直接成为季军
对应代码如下
# nums的长度是3，那么A和B争夺冠亚军
# 如果B的实力强过A，那么两者位置交换
if len(nums) == 3:
if nums[1][0] > nums[0][0]:
nums[0], nums[1] = nums[1], nums[0]
print(" ".join((str(idx) for num, idx in nums)))- 剩下
4个人，假设这三个人按照id大小排序分别为A B C D。这就是示例所给出的情况A和B进行比赛，C和D进行比赛- 上述比赛中的两个胜者进行冠军争夺战，胜者为冠军，败者为亚军
- 上述比赛中的两个败者进行季军争夺战，胜者为季军
对应代码如下
# nums的长度是4，那么需要先进行A和B、C和D之间的两两比较
if len(nums) == 4:
A, B, C, D = nums
# A和B之间比较
# 若A是胜者，那么
# 将A放到nums[0]的位置，后续进行冠军争夺
# 将B放到nums[2]的位置，后续进行季军争夺
if A[0] >= B[0]:
nums[0] = A
nums[2] = B
# 若B是胜者，那么
# 将B放到nums[0]的位置，后续进行冠军争夺
# 将A放到nums[2]的位置，后续进行季军争夺
else:
nums[0] = B
nums[2] = A
# C和D之间比较
# 若C是胜者，那么
# 将C放到nums[1]的位置，后续进行冠军争夺
# 将D放到nums[3]的位置，后续进行季军争夺
if C[0] >= D[0]:
nums[1] = C
nums[3] = D
# 若D是胜者，那么
# 将D放到nums[1]的位置，后续进行冠军争夺
# 将C放到nums[3]的位置，后续进行季军争夺
else:
nums[1] = D
nums[3] = C
# 以下进行冠亚军争夺
if nums[1][0] > nums[0][0]:
nums[0], nums[1] = nums[1], nums[0]
# 以下进行季军争夺
if nums[3][0] > nums[2][0]:
nums[2], nums[3] = nums[3], nums[2]
# 输出前三名的id
print(" ".join((str(idx) for num, idx in nums[:3])))PS：本题的题目描述非常模糊，有不少同学提出异议。
对于最后决胜轮次的比拼规则，只能按照唯一的示例进行猜测。
如果关于最后剩余人数为3的情况的冠亚季军角逐的比赛顺序为：先进行A跟B的比拼，败者为季军，其中胜者再跟轮空的C进行比拼决出冠亚军。那么对应的代码则修改为
# nums的长度是3，那么A和B先进行一轮比拼，败者为季军
# 如果B的实力强过A，那么两者位置交换
if len(nums) == 3:
A, B, C = nums
# A和B之间比较
# 若A是胜者，那么
# 将A放到nums[0]的位置，后续进行冠军争夺
# 将B放到nums[2]的位置，为季军
if A[0] >= B[0]:
nums[0] = A
nums[2] = B
# 若B是胜者，那么
# 将B放到nums[0]的位置，后续进行冠军争夺
# 将A放到nums[2]的位置，为季军
else:
nums[0] = B
nums[2] = A
# C轮空，直接可以进行冠军争夺
nums[1] = C
# 以下进行冠亚军争夺，为A和B之间的胜者与C的比拼
if nums[1][0] > nums[0][0]:
nums[0], nums[1] = nums[1], nums[0]
# 输出前三名的id
print(" ".join((str(idx) for num, idx in nums)))要学会能够自己根据不同的模糊题意描述进行代码的修改和测试。
代码
Python
# 题目：【模拟】比赛的冠亚季军
# 分值：100
# 作者：许老师-闭着眼睛学数理化
# 算法：模拟
# 代码看不懂的地方，请直接在群上提问
# 输入
nums = list(map(int, input().split()))
# 同时储存实力num和原编号i
nums = [(num, idx) for idx, num in enumerate(nums)]
# 进行若干次循环，退出循环的条件是nums的长度小于5
# 经过若干轮比拼之后，nums的最终长度会是3或4
while len(nums) >= 5:
# 构建一个空列表，用于储存该轮比赛的结果
nums_new = list()
# 遍历当前的nums数组，注意步长取2，表示每次取相邻的两个人进行比赛
# 前一个人为nums[i]，后一个人为nums[i+1]
for i in range(0, len(nums)-1, 2):
# 如果比赛之后，前一个人的实力大于等于后一个的实力
# 则将前一个人的情况加入nums_new中
# 注意：这里之所以是≥，是因为题目要求当两个人实力相等时，认为是id小的获胜
if nums[i][0] >= nums[i+1][0]:
nums_new.append(nums[i])
# 否则将后一个人的情况加入nums_new中
else:
nums_new.append(nums[i+1])
# 如果nums的长度是奇数，说明最后一个人轮空，必须加入下一轮
if len(nums) % 2 == 1:
nums_new.append(nums[-1])
# 最后，重置nums为nums_new，用于下一个循环操作
nums = nums_new
# 经过若干轮比拼之后，nums的最终长度会是3或4，进行分类讨论
# nums的长度是3，那么A和B争夺冠亚军
# 如果B的实力强过A，那么两者位置交换
if len(nums) == 3:
if nums[1][0] > nums[0][0]:
nums[0], nums[1] = nums[1], nums[0]
print(" ".join((str(idx) for num, idx in nums)))
# nums的长度是4，那么需要先进行A和B、C和D之间的两两比较
elif len(nums) == 4:
A, B, C, D = nums
# A和B之间比较
# 若A是胜者，那么
# 将A放到nums[0]的位置，后续进行冠军争夺
# 将B放到nums[2]的位置，后续进行季军争夺
if A[0] >= B[0]:
nums[0] = A
nums[2] = B
# 若B是胜者，那么
# 将B放到nums[0]的位置，后续进行冠军争夺
# 将A放到nums[2]的位置，后续进行季军争夺
else:
nums[0] = B
nums[2] = A
# C和D之间比较
# 若C是胜者，那么
# 将C放到nums[1]的位置，后续进行冠军争夺
# 将D放到nums[3]的位置，后续进行季军争夺
if C[0] >= D[0]:
nums[1] = C
nums[3] = D
# 若D是胜者，那么
# 将D放到nums[1]的位置，后续进行冠军争夺
# 将C放到nums[3]的位置，后续进行季军争夺
else:
nums[1] = D
nums[3] = C
# 以下进行冠亚军争夺
if nums[1][0] > nums[0][0]:
nums[0], nums[1] = nums[1], nums[0]
# 以下进行季军争夺
if nums[3][0] > nums[2][0]:
nums[2], nums[3] = nums[3], nums[2]
# 输出前三名的id
print(" ".join((str(idx) for num, idx in nums[:3])))Java
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String[] input = scanner.nextLine().split(" ");
int[] nums = new int[input.length];
for (int i = 0; i < input.length; i++) {
nums[i] = Integer.parseInt(input[i]);
}
int n = nums.length;
int[] index = new int[n];
for (int i = 0; i < n; i++) {
index[i] = i;
}
int[] newNums;
while (n >= 5) {
newNums = new int[(n + 1) / 2];
for (int i = 0; i < n - 1; i += 2) {
if (nums[i] >= nums[i + 1]) {
newNums[i / 2] = nums[i];
index[i / 2] = index[i];
} else {
newNums[i / 2] = nums[i + 1];
index[i / 2] = index[i + 1];
}
}
if (n % 2 == 1) {
newNums[n / 2] = nums[n - 1];
index[n / 2] = index[n - 1];
}
nums = newNums;
n = (n + 1) / 2;
}
if (n == 3) {
if (nums[1] > nums[0]) {
int temp = nums[0];
nums[0] = nums[1];
nums[1] = temp;
temp = index[0];
index[0] = index[1];
index[1] = temp;
}
System.out.println((index[0]) + " " + (index[1]) + " " + (index[2]));
} else if (n == 4) {
int A, B, C, D;
A = nums[0];
B = nums[1];
C = nums[2];
D = nums[3];
int indexA, indexB, indexC, indexD;
indexA = index[0];
indexB = index[1];
indexC = index[2];
indexD = index[3];
if (A >= B) {
nums[0] = A;
index[0] = indexA;
nums[2] = B;
index[2] = indexB;
} else {
nums[0] = B;
index[0] = indexB;
nums[2] = A;
index[2] = indexA;
}
if (C >= D) {
nums[1] = C;
index[1] = indexC;
nums[3] = D;
index[3] = indexD;
} else {
nums[1] = D;
index[1] = indexD;
nums[3] = C;
index[3] = indexC;
}
if (nums[1] > nums[0]) {
int temp = nums[0];
nums[0] = nums[1];
nums[1] = temp;
temp = index[0];
index[0] = index[1];
index[1] = temp;
}
if (nums[3] > nums[2]) {
int temp = nums[2];
nums[2] = nums[3];
nums[3] = temp;
temp = index[2];
index[2] = index[3];
index[3] = temp;
}
System.out.println((index[0]) + " " + (index[1]) + " " + (index[2]));
}
}
}C++
#include <iostream>
#include <sstream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
vector<pair<int, int>> nums;
string input;
getline(cin, input);
istringstream iss(input);
int num, idx = 0;
while (iss >> num) {
nums.push_back(make_pair(num, idx));
idx++;
}
while (nums.size() >= 5) {
vector<pair<int, int>> newNums;
for (size_t i = 0; i < nums.size() - 1; i += 2) {
if (nums[i].first >= nums[i + 1].first) {
newNums.push_back(nums[i]);
} else {
newNums.push_back(nums[i + 1]);
}
}
if (nums.size() % 2 == 1) {
newNums.push_back(nums[nums.size() - 1]);
}
nums = newNums;
}
if (nums.size() == 3) {
if (nums[1].first > nums[0].first){
swap(nums[0], nums[1]);
}
for (size_t i = 0; i < 3; i++) {
cout << nums[i].second << " ";
}
cout << endl;
} else if (nums.size() == 4) {
pair<int, int> A, B, C, D;
A = nums[0];
B = nums[1];
C = nums[2];
D = nums[3];
if (A.first >= B.first) {
nums[0] = A;
nums[2] = B;
} else {
nums[0] = B;
nums[2] = A;
}
if (C.first >= D.first) {
nums[1] = C;
nums[3] = D;
} else {
nums[1] = D;
nums[3] = C;
}
if (nums[1].first > nums[0].first) {
swap(nums[0], nums[1]);
}
if (nums[3].first > nums[2].first) {
swap(nums[2], nums[3]);
}
for (size_t i = 0; i < 3; i++) {
cout << nums[i].second << " ";
}
cout << endl;
}
return 0;
}C
#include <stdio.h>
#include <stdlib.h>
// 定义一个结构体用于存储选手的实力和编号
typedef struct {
int strength; // 实力
int index; // 编号
} Player;
// 定义比较函数，用于根据选手的实力和编号排序
int comparePlayers(const void *a, const void *b) {
Player *p1 = (Player *)a;
Player *p2 = (Player *)b;
if (p1->strength != p2->strength) {
return p2->strength - p1->strength; // 按实力降序排序
}
return p1->index - p2->index; // 实力相同时按编号升序排序
}
// 主函数
int main() {
// 输入选手的实力值
int n = 0;
int nums[10001];
while (scanf("%d", &nums[n]) != EOF) {
n++;
}
// 初始化选手数组
Player players[10001];
for (int i = 0; i < n; i++) {
players[i].strength = nums[i];
players[i].index = i;
}
// 模拟比赛
while (n >= 5) {
int newN = (n + 1) / 2;
Player newPlayers[100];
for (int i = 0, j = 0; i < n - 1; i += 2, j++) {
// 两两比较选手，胜者进入下一轮
if (players[i].strength > players[i + 1].strength ||
(players[i].strength == players[i + 1].strength && players[i].index < players[i + 1].index)) {
newPlayers[j] = players[i];
} else {
newPlayers[j] = players[i + 1];
}
}
// 如果人数为奇数，最后一人直接晋级
if (n % 2 == 1) {
newPlayers[newN - 1] = players[n - 1];
}
// 更新选手数组
for (int i = 0; i < newN; i++) {
players[i] = newPlayers[i];
}
n = newN;
}
// 根据剩余选手人数分类处理
if (n == 3) {
// 如果选手人数为3，比较冠亚军
if (players[1].strength > players[0].strength) {
Player temp = players[0];
players[0] = players[1];
players[1] = temp;
}
// 输出前三名的编号
printf("%d %d %d\n", players[0].index, players[1].index, players[2].index);
} else if (n == 4) {
// 如果选手人数为4，先两两比较
Player A = players[0], B = players[1], C = players[2], D = players[3];
if (A.strength < B.strength || (A.strength == B.strength && A.index > B.index)) {
Player temp = A;
A = B;
B = temp;
}
if (C.strength < D.strength || (C.strength == D.strength && C.index > D.index)) {
Player temp = C;
C = D;
D = temp;
}
// 冠亚军决赛
if (C.strength > A.strength || (C.strength == A.strength && C.index < A.index)) {
Player temp = A;
A = C;
C = temp;
}
// 季军决赛
if (D.strength > B.strength || (D.strength == B.strength && D.index < B.index)) {
Player temp = B;
B = D;
D = temp;
}
// 输出前三名的编号
printf("%d %d %d\n", A.index, C.index, B.index);
}
return 0;
}Node JavaScript
// 导入 readline 模块以便读取用户输入
const readline = require("readline");
// 创建接口以读取输入
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});
// 主函数
rl.question("", (line) => {
// 将输入的字符串转化为数字数组
let nums = line.split(" ").map((num, idx) => [parseInt(num), idx]);
// 循环处理，直到数组长度小于 5
while (nums.length >= 5) {
let numsNew = [];
// 遍历当前数组，两两进行比赛
for (let i = 0; i < nums.length - 1; i += 2) {
// 如果前一个人的实力大于等于后一个人的实力
// 则前一个人获胜，否则后一个人获胜
if (nums[i][0] >= nums[i + 1][0]) {
numsNew.push(nums[i]);
} else {
numsNew.push(nums[i + 1]);
}
}
// 如果数组长度为奇数，最后一人直接晋级
if (nums.length % 2 === 1) {
numsNew.push(nums[nums.length - 1]);
}
// 更新数组为新一轮的结果
nums = numsNew;
}
// 数组长度为 3 时，A 和 B 比较争夺冠亚军
if (nums.length === 3) {
if (nums[1][0] > nums[0][0]) {
// 如果 B 实力强过 A，交换位置
[nums[0], nums[1]] = [nums[1], nums[0]];
}
// 输出前三名的编号
console.log(nums.map(pair => pair[1]).join(" "));
}
// 数组长度为 4 时，进行两两比较
else if (nums.length === 4) {
let [A, B, C, D] = nums;
// A 和 B 比较，胜者争冠，败者争季
if (A[0] >= B[0]) {
nums[0] = A;
nums[2] = B;
} else {
nums[0] = B;
nums[2] = A;
}
// C 和 D 比较，胜者争冠，败者争季
if (C[0] >= D[0]) {
nums[1] = C;
nums[3] = D;
} else {
nums[1] = D;
nums[3] = C;
}
// 冠亚军争夺
if (nums[1][0] > nums[0][0]) {
[nums[0], nums[1]] = [nums[1], nums[0]];
}
// 季军争夺
if (nums[3][0] > nums[2][0]) {
[nums[2], nums[3]] = [nums[3], nums[2]];
}
// 输出前三名的编号
console.log(nums.slice(0, 3).map(pair => pair[1]).join(" "));
}
rl.close(); // 关闭输入接口
});Go
package main
import (
"bufio"
"fmt"
"os"
"strconv"
"strings"
)
func main() {
// 创建读取器，读取输入
reader := bufio.NewReader(os.Stdin)
line, _ := reader.ReadString('\n')
line = strings.TrimSpace(line)
// 将输入字符串转换为整数数组，同时储存实力值和原编号
strNums := strings.Split(line, " ")
nums := make([][2]int, len(strNums))
for i, str := range strNums {
val, _ := strconv.Atoi(str)
nums[i] = [2]int{val, i} // 数组中存储实力值和原编号
}
// 进行若干次循环，直到数组长度小于5
for len(nums) >= 5 {
numsNew := make([][2]int, 0)
// 遍历当前数组，两两进行比赛
for i := 0; i < len(nums)-1; i += 2 {
if nums[i][0] >= nums[i+1][0] {
// 前一个人的实力大于等于后一个人，将前一个加入结果
numsNew = append(numsNew, nums[i])
} else {
// 否则将后一个加入结果
numsNew = append(numsNew, nums[i+1])
}
}
// 如果数组长度为奇数，最后一个人直接晋级
if len(nums)%2 == 1 {
numsNew = append(numsNew, nums[len(nums)-1])
}
nums = numsNew
}
// 如果数组长度为3，处理冠亚军争夺
if len(nums) == 3 {
if nums[1][0] > nums[0][0] {
nums[0], nums[1] = nums[1], nums[0] // 交换A和B
}
// 输出结果
fmt.Printf("%d %d %d\n", nums[0][1], nums[1][1], nums[2][1])
} else if len(nums) == 4 { // 如果数组长度为4
A, B, C, D := nums[0], nums[1], nums[2], nums[3]
// A和B争夺，胜者争冠，败者争季
if A[0] >= B[0] {
nums[0] = A
nums[2] = B
} else {
nums[0] = B
nums[2] = A
}
// C和D争夺，胜者争冠，败者争季
if C[0] >= D[0] {
nums[1] = C
nums[3] = D
} else {
nums[1] = D
nums[3] = C
}
// 冠亚军争夺
if nums[1][0] > nums[0][0] {
nums[0], nums[1] = nums[1], nums[0]
}
// 季军争夺
if nums[3][0] > nums[2][0] {
nums[2], nums[3] = nums[3], nums[2]
}
// 输出前三名编号
fmt.Printf("%d %d %d\n", nums[0][1], nums[1][1], nums[2][1])
}
}时空复杂度
时间复杂度：O(NlogN)。
空间复杂度：O(N)。