淘汰赛：区间最大值贪心解法

一、 题目大意

• 核心描述：

一共有 2n 个国家参加单场淘汰赛，两两配对比赛，能力值高的一方必胜，一直比赛直到决出冠军。比赛顺序：1 和 2 比、3 和 4 比…… 相邻编号两两对决，胜者晋级继续淘汰赛。已知所有国家的能力值互不相同，求最终亚军的国家编号

• 样例说明：

样例输入 n=3，总共有 23=8 个国家。8 个国家能力依次为：1 号：4，2 号：2，3 号：3，4 号：1，5 号：10，6 号：5，7 号：9，8 号：7整个赛程里冠军是 5 号，和冠军在决赛对战的对手就是亚军，也就是1 号，所以输出 1

二、 思路解析（核心部分）

第一层：解题基石

• 贪心思想 + 简单遍历找最大值：

本题不需要模拟完整淘汰赛全过程，仅用基础遍历即可解决

• 选择原因：

1.淘汰赛的赛程结构是严格的完全二叉树，所有队伍被均匀分成左右两个半区

2.冠军必然是两个半区各自的最强者之一

3.亚军一定是另外一个半区里的最强队伍

4.数据范围 n≤7，总人数最多 2^7=128，数据极小，暴力遍历完全足够

第二层：思维脉络

• 关键步骤拆解：

1.计算总参赛队伍数量:tot=2^n

2.将所有队伍平均划分为左半区、右半区两部分

3.分别遍历两个半区，找出左半区能力最强的编号、右半区能力最强的编号

4.两个最强队伍中，能力较弱的那一个，就是最终亚军

• 状态定义：

本题无动态规划，无需 DP 数组定义

• 核心公式/推导：

可设：

maxL = 左半区最大能力值，idL = 对应编号

maxR = 右半区最大能力值，idR = 对应编号决赛对决

则：

max(maxL,maxR) 对应编号为冠军

min(maxL,maxR) 对应编号为亚军

第三层：难点与陷阱

• 本题的易错点：

1.浮点数精度使用错误：使用 pow(2,n) 计算队伍总数，pow 是浮点函数，会出现 128 变成 127.9999 的误差，导致数组越界

2.错误模拟全程比赛：当一层层模拟晋级时，代码写复杂还容易写错

3.混淆能力值和国家编号，只存数值忘记记录原始编号

4.数组下标混乱，左右半区分割错误

• 你是如何思考的：

观察淘汰赛树形结构发现规律：亚军只会是决赛输家，而决赛双方分别是左右两大区的最强者，因此完全不需要模拟全程比赛，只需要找两个大区最大值，弱者即为答案，思路大幅简化。

三、 代码实现

• 代码：

  #include<bits/stdc++.h>
  using namespace std;
  
  int main()
  {
      freopen("knockout.in","r",stdin);
      freopen("knockout.out","w",stdout);
      ios::sync_with_stdio(false);
      cin.tie(0);
      
      int n;
      cin >> n;
      int total = 1 << n;    // 等价于 2^n，整数位运算，无浮点精度误差
      int half = total / 2; // 左右半区分界线
      
      int val[130]; // 下标代表国家编号，值代表能力
      for(int i = 1; i <= total; i++)
      {
          cin >> val[i];
      }
  
      // 寻找左半区(1~half)能力最强的编号
      int maxL = -1, idL = 0;
      for(int i = 1; i <= half; i++)
      {
          if(val[i] > maxL)
          {
              maxL = val[i];
              idL = i;
          }
      }
  
      // 寻找右半区(half+1~total)能力最强的编号
      int maxR = -1, idR = 0;
      for(int i = half + 1; i <= total; i++)
      {
          if(val[i] > maxR)
          {
              maxR = val[i];
              idR = i;
          }
      }
  
      // 两者中能力更小的就是亚军
      if(maxL < maxR) cout << idL;
      else cout << idR;
      
      return 0;
  }
  

• 复杂度分析：
  • 时间复杂度：O(2^n)

  原因：仅遍历一遍所有参赛国家寻找最大值，每个元素访问一次。

  • 空间复杂度：O(2^n)

  原因：用数组存储所有国家的能力值，数组大小为 2^n

四、 总结与反思（升华部分）

• 收获与心得：

1.透过赛程结构找规律，不用死板模拟全过程，淘汰赛树形结构有固定结论：亚军是决赛对手，即另一半区最强者

2.规避 pow() 函数浮点误差的技巧：用位运算 1<<n 计算 2n

3.理解单胜者淘汰赛、完全二叉树比赛模型的通用性质

• 举一反三：

本题结论可以迁移到所有相邻配对、强者必胜、单败淘汰赛题目：

1.求决赛两支队伍

2.求四强、八强分别是谁

3.同类体育竞赛赛程推理题目。

• 待优化空间：

1.可以封装函数实现通用区间最大值查找，代码复用性更高

2.可以扩展写法，模拟完整每一轮晋级过程，输出每一轮晋级名单，验证规律

3.若题目改为弱者获胜，只需修改大小比较符号即可，整体思路不变。

五、 推荐题目

• 603. 网球赛 http://172.30.1.3/cogs/problem/problem.php?pid=pmzSJieaj