题解 洛谷 Luogu P4715 【深基16.例1】淘汰赛 C++

题目

传送门

P4715 【深基16.例1】淘汰赛 - 洛谷 | 计算机科学教育新生态https://www.luogu.com.cn/problem/P4715https://www.luogu.com.cn/problem/P4715https://www.luogu.com.cn/problem/P4715https://www.luogu.com.cn/problem/P4715

思路

2^7 也就 128 个数据，直接暴力模拟决出胜者的过程就行了

每轮操作，数组中的元数数量减半，仅保留特定下标组中能力值较大的那个

特定下标组，就是题目所说的某场比赛中参赛二国对应的下标

如剩 8 个参赛国时，有 (0, 1), (2, 3), (4, 5), (6, 7) 四个下标组，分别存入 0, 1, 2, 3

只剩两个参赛国时，输出能力值较小者的编号

因为能力值和编号绑定，我们存的时候把它们两个存一起，用 pair<int, int> 就行了

pair 对象之间默认的大小比较 (本题体现在 max(a, b) 和最后的比较语句)

first 的优先级高于 second，只有两对象 first 相等时才会比较 second

题目说了不同参赛国能力值不同

这样的存储方式下，pair 对象之间默认的大小比较与我们的模拟目标相符

代码

#include <algorithm>
#include <cmath>
#include <iostream>
using namespace std;
typedef pair<int, int> PII;
const int N = 1030;
int n, POW, ans;
PII arr[N];
int main()
{
    cin >> n;
    POW = pow(2, n); //pow(2, n) 提前计算，避免放在循环条件中带来的额外计算开销 (循环条件每次循环体执行完都会执行)
    for (int i = 0; i < POW; i++)
        cin >> arr[i].first, arr[i].second = i + 1; //second 存编号
    while ((POW /= 2) >= 2) //POW 表示该轮要保留的参赛国的数量，每轮 / 2，最后一轮要保留 2 个参赛国
        for (int i = 0; i < POW; i++)
            arr[i] = max(arr[i * 2], arr[i * 2 + 1]); //模拟决出胜者的过程。(i * 2, i * 2 + 1) 是一个特定下标组，存入 i
    cout << (arr[0] < arr[1] ? arr[0].second : arr[1].second); //输出最后 2 个参赛国中能力值较小的参赛国的编号
    return 0;
}