题目描述

有 N 个运动员，他们的 id 为 0 到 N-1 。每位运动员的实力值用一个正整数表示。所有运动员按照如下规则进行比赛，最终决出冠亚季军：

1. 每轮比赛中，相邻的运动员进行比赛，胜者进入下一轮。实力值大的运动员获胜；若实力值相等，id 小的获胜。
2. 如果当前轮比赛中有奇数个运动员，则最后一个运动员轮空，直接进入下一轮。
3. 比赛进行到最终的两名运动员时，获胜者为冠军，失败者为亚军。随后，亚军和上一轮被淘汰的运动员中实力最强的进行比赛，胜者为季军。

解题思路

1. 使用递归的方式模拟比赛过程，逐轮减少选手数量。
2. 对于每一轮比赛，比较相邻选手，获胜者进入下一轮；若选手数量为奇数，最后一名直接晋级。
3. 比赛进行到最终两人时，记录冠亚军的 id，并决定季军为上一轮中实力最强的未进入冠亚军的选手。
4. 返回冠亚季军的 id。

代码实现

Python代码

def cmp(x, y):
    # 比较两名选手，返回实力强者和弱者（以tuple形式）
    if x[0] > y[0]:  # 实力高者胜
        return (x, y)
    elif x[0] < y[0]:  # 实力低者败
        return (y, x)
    else:  # 实力相等，id 小者胜
        if x[1] < y[1]:
            return (x, y)
        else:
            return (y, x)

def solve(players):
    n = len(players)
    if n == 3:  # 特殊情况：只有三名选手
        k1 = cmp(players[0], players[1])  # 比较前两名
        k2 = cmp(k1[0], players[2]) # 冠亚军
        return [k2[0][1], k2[1][1], k1[1][1]]
    elif n == 4:  # 特殊情况：四名选手
        k1 = cmp(players[0], players[1])
        k2 = cmp(players[2], players[3])
        k3 = cmp(k1[0], k2[0])  # 冠亚军
        k4 = cmp(k1[1], k2[1])  # 季军争夺
        return [k3[0][1], k3[1][1], k4[0][1]]
    
    win_players = []
    for i in range(1, n, 2):  # 每两名选手比赛
        win_players.append(cmp(players[i-1],players[i])[0])
    if n % 2 == 1:  # 奇数时最后一人轮空晋级
        win_players.append(players[-1])
    
    return solve(win_players)

# 输入处理
p = [int(i) for i in input().split()]
players = [(p[i], i) for i in range(len(p))]
print(' '.join([str(i) for i in solve(players)]))

Java代码

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // 创建扫描器对象，用于读取输入
        Scanner sc = new Scanner(System.in);
        
        // 读取一行输入并用空格分割
        String[] input = sc.nextLine().split(" ");
        int n = input.length;  // 选手数量
        Long[][] players = new Long[n][2];  // 用 Long 类型表示选手数据（实力值和选手ID）
        
        // 将输入的数据填充到 players 数组中
        for (int i = 0; i < n; i++) {
            players[i][0] = Long.parseLong(input[i]);  // 解析实力值为 Long 类型
            players[i][1] = (long) i;  // 选手的 ID（从 0 开始）
        }
        
        // 调用 solve 方法进行比赛并输出结果
        List<Long> result = solve(players);
        System.out.println(result.get(0) + " " + result.get(1) + " " + result.get(2));
    }
    
    // solve 方法根据选手数据进行比赛，返回冠军、亚军和季军
    public static List<Long> solve(Long[][] players) {
        int n = players.length;  // 获取选手数量
        
        // 特殊情况：当选手数量为 3 时，直接进行比赛
        if (n == 3) {
            Long[][] k1 = cmp(players[0], players[1]);  // 第一轮比赛，比较前两位选手
            Long[][] k2 = cmp(k1[0], players[2]);  // 冠军与第三位选手对决
            return Arrays.asList(k2[0][1], k2[1][1], k1[1][1]);  // 返回冠军、亚军和季军的 ID
        } 
        // 特殊情况：当选手数量为 4 时，进行两轮比赛
        else if (n == 4) {
            Long[][] k1 = cmp(players[0], players[1]);  // 第一轮比赛，前两位选手
            Long[][] k2 = cmp(players[2], players[3]);  // 第二轮比赛，后两位选手
            Long[][] k3 = cmp(k1[0], k2[0]);  // 冠亚军对决
            Long[][] k4 = cmp(k1[1], k2[1]);  // 季军争夺
            return Arrays.asList(k3[0][1], k3[1][1], k4[0][1]);  // 返回冠军、亚军和季军的 ID
        }
        
        // 进行递归比赛，处理选手数大于 4 的情况
        List<Long[]> winPlayers = new ArrayList<>();
        for (int i = 1; i < n; i += 2) {
            winPlayers.add(cmp(players[i - 1], players[i])[0]);  // 每对选手进行比较，记录胜者
        }
        // 如果选手数量是奇数，最后一名选手自动进入下一轮
        if (n % 2 == 1) {
            winPlayers.add(players[n - 1]);
        }
        
        // 递归处理剩下的选手，直到剩下 3 个选手
        return solve(winPlayers.toArray(new Long[0][]));
    }
    
    // 比较两名选手，返回实力强者和弱者
    public static Long[][] cmp(Long[] x, Long[] y) {
        // 如果 x 的实力值大于 y，或者相等时 x 的 ID 小于 y，返回 x 强
        if (x[0] > y[0] || (x[0] == y[0] && x[1] < y[1])) {
            return new Long[][] {x, y};
        } else {
            return new Long[][] {y, x};  // 否则返回 y 强
        }
    }
}

C++代码

#include <iostream>
#include <vector>
#include <algorithm>
#define LL long long
using namespace std;

// 比较两名选手，返回实力强者和弱者
pair<pair<LL, LL>, pair<LL, LL>> cmp(pair<LL, LL> x, pair<LL, LL> y) {
    if (x.first > y.first || (x.first == y.first && x.second < y.second)) {
        return {{x.first, x.second}, {y.first, y.second}};
    } else {
        return {{y.first, y.second}, {x.first, x.second}};
    }
}

vector<LL> solve(vector<pair<LL, LL>>& players) {
    LL n = players.size();
    if (n == 3) {
        auto k1 = cmp(players[0], players[1]);
        auto k2 = cmp(k1.first, players[2]); // 冠亚军
        return {k2.first.second, k2.second.second, k1.second.second};
    } else if (n == 4) {
        auto k1 = cmp(players[0], players[1]);
        auto k2 = cmp(players[2], players[3]);
        auto k3 = cmp(k1.first, k2.first); // 冠亚军
        auto k4 = cmp(k1.second, k2.second); // 季军争夺
        return {k3.first.second, k3.second.second, k4.first.second};
    }

    vector<pair<LL, LL>> winPlayers;
    for (LL i = 1; i < n; i += 2) {
       winPlayers.push_back(cmp(players[i - 1], players[i]).first);
    }
    if (n % 2 == 1) {
        winPlayers.push_back(players[n - 1]);
    }
    return solve(winPlayers);
}

int main() {
    LL n;
    vector<pair<LL, LL>> players;
    LL val;
    while (cin >> val) {
        players.emplace_back(val, players.size());
    }
    vector<LL> result = solve(players);
    for (LL i = 0; i < result.size(); ++i) {
        cout << result[i];
        if (i < result.size() - 1) cout << " ";
    }
    return 0;
}

题目内容

有 $N（3 ≤ N < 10000）$个运动员，他们的 $id$ 为 $0$ 到 $N-1$ ,他们的实力由一组整数表示。 他们之间进行比赛，需要决出冠亚军。比赛的规则是 $0$ 号和 $1$ 号比赛，$2$ 号和 $3$ 号比赛，以此类推，每一轮，相邻的运动员进行比赛，获胜的进入下一轮；实力值大的获胜，实力值相等的情况， $id$ 小的情况下获胜；轮空的直接进入下一轮。

输入描述

输入一行 $N$ 个数字代表 $N$ 个运动员的实力值($0<=$实力值$<=10000000000$)。

输出描述

输出冠亚季军的 $id$ ，用空格隔开。

样例1

输入

2 3 4 5

输出

3 1 2

说明

第一轮比赛，

$id$ 为 $0$ 实力值为 $2$ 的运动员和 $id$ 为 $1$ 实力值为 $3$ 的运动员比赛，$1$ 号胜出进入下一轮争夺冠亚军，

$id$ 为 $2$ 的运动员和 $id$ 为 $3$ 的运动员比赛， $3$ 号胜出进入下一轮争夺冠亚军，

冠亚军比赛，$3$ 号胜 $1$ 号，

故冠军为 $3$ 号，亚军为 $1$ 号，$2$ 号与 $0$ 号，比赛进行季军的争夺， $2$ 号实力值为 $4$ ，$0$ 号实力值 $2$ ，故 $2$ 号胜出，得季军。

冠亚季军为 $3$ $1$ $2$。