厦门大学夏令营机试第三题-淘汰赛

题目描述

有多个国家进行比赛，每个国家有个战力值，两两进行比赛，战力值高的获胜，求获得亚军的国家是哪个。比如有四个国家，A和B比，C和D比，最后获胜的两个国家再两两比较，求最终的亚军国家。

题解

比赛过程如下：

1. 按照输入顺序进行两两比较，胜者进入下一轮。
2. 重复上述过程直到只剩下两个国家。
3. 两个国家进行决赛，决赛的失败者即为亚军。

代码实现

下面是实现上述逻辑的C++代码：

#include <iostream>
#include <climits>
using namespace std;

const int maxn = 100; // 最大国家数量
const int INF = INT_MAX; // 用于标记无穷大

int n, a[maxn], tmp[maxn << 1]; // tmp数组大小为a的两倍

// 比赛函数，返回获胜的战力值位置
int winner(int pos1, int pos2) {
    int u = pos1 >= n ? pos1 : tmp[pos1];
    int v = pos2 >= n ? pos2 : tmp[pos2];
    if (tmp[u] >= tmp[v]) return u;
    return v;
}

void create_tree(int &champion, int &runner_up) {
    // 将国家的战力值复制到 tmp 数组的后半部分
    for (int i = 0; i < n; i++) tmp[n + i] = a[i];
    // 从底层向上构建淘汰树
    for (int i = 2 * n - 1; i > 1; i -= 2) {
        int k = i / 2;
        int j = i - 1;
        tmp[k] = winner(i, j);
    }
    champion = tmp[tmp[1]];

    // 找到亚军：在tmp[2]和tmp[3]中较小的值
    int pos2 = 2, pos3 = 3;
    int final_pos2 = (tmp[pos2] >= n) ? tmp[pos2] : tmp[tmp[pos2]];
    int final_pos3 = (tmp[pos3] >= n) ? tmp[pos3] : tmp[tmp[pos3]];
    runner_up = (tmp[final_pos2 ] > tmp[final_pos3 ]) ? tmp[final_pos3] : tmp[final_pos2];
}

int main() {
    cout << "请输入国家数量: ";
    cin >> n;

    cout << "请输入各国家的战力值: ";
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    int champion_value, runner_up_value;
    create_tree(champion_value, runner_up_value);

    cout << "冠军的战力值是: " << champion_value << endl;
    cout << "亚军的战力值是: " << runner_up_value << endl;

    return 0;
}

代码解释

这段代码实现了一个比赛淘汰树，用来找出一组国家中的冠军和亚军。以下是对代码的详细解释：

引入头文件和命名空间

#include <iostream>
#include <climits>
using namespace std;

• 引入标准输入输出库<iostream>，以及<climits>用于获取整型的最大值。
• 使用std命名空间，方便后续代码编写。

定义常量和变量

const int maxn = 100; // 最大国家数量
const int INF = INT_MAX; // 用于标记无穷大

int n, a[maxn], tmp[maxn << 1]; // tmp数组大小为a的两倍

• maxn定义了最多可以有100个国家。
• INF表示无穷大，使用系统提供的INT_MAX。
• n表示国家的数量，a数组存储每个国家的战力值，tmp数组是a数组大小的两倍，用于构建淘汰树。

比赛函数

int winner(int pos1, int pos2) {
    int u = pos1 >= n ? pos1 : tmp[pos1];
    int v = pos2 >= n ? pos2 : tmp[pos2];
    if (tmp[u] >= tmp[v]) return u;
    return v;
}

• winner函数用于返回两个位置中战力值较大的那个。
• 如果位置大于等于n，说明已经在tmp数组后半部分，直接取pos1或pos2的值，否则取tmp中的值。
• 比较两个值，返回较大的那个位置。

构建淘汰树并找出冠军和亚军

void create_tree(int &champion, int &runner_up) {
    for (int i = 0; i < n; i++) tmp[n + i] = a[i];
    for (int i = 2 * n - 1; i > 1; i -= 2) {
        int k = i / 2;
        int j = i - 1;
        tmp[k] = winner(i, j);
    }
    champion = tmp[tmp[1]];

    int pos2 = 2, pos3 = 3;
    int final_pos2 = (tmp[pos2] >= n) ? tmp[pos2] : tmp[tmp[pos2]];
    int final_pos3 = (tmp[pos3] >= n) ? tmp[pos3] : tmp[tmp[pos3]];
    runner_up = (tmp[final_pos2] > tmp[final_pos3]) ? tmp[final_pos3] : tmp[final_pos2];
}

• 首先，将国家的战力值复制到tmp数组的后半部分。
• 然后，从底层向上构建淘汰树。每次取两个位置进行比较，存储较大值的位置到上一级位置。
• 最后，找到冠军，即tmp[1]所对应的值。
• 找到亚军的方法：在tmp[2]和tmp[3]中较小的值，即冠军的左右子树中次优的那个值。

主函数

int main() {
    cout << "请输入国家数量: ";
    cin >> n;

    cout << "请输入各国家的战力值: ";
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    int champion_value, runner_up_value;
    create_tree(champion_value, runner_up_value);

    cout << "冠军的战力值是: " << champion_value << endl;
    cout << "亚军的战力值是: " << runner_up_value << endl;

    return 0;
}

• 主函数负责读取输入，并调用create_tree函数找出冠军和亚军。
• 读取国家数量n和各国家的战力值a。
• 调用create_tree函数，并输出冠军和亚军的战力值。

这段代码通过构建一棵淘汰树，高效地找出了冠军和亚军的战力值。