P4715. 淘汰赛

发表于 更新于 分类于 阅读次数： Waline： 本文字数： 268 阅读时长 ≈ 1 分钟

考点

  • 二叉树

# 题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <bits/stdc++.h>
using namespace std;
const int LEN = 1024;
int N;

struct Node
{
    int id_, v_;
} arr[4 * LEN];

#define rt arr[root]

Node dfs(int root)
{
    //如果当前是叶子结点，直接返回
    if (root >= (1 << N))
        return rt;
    //递归建立左子树、右子树，最后才建立父结点
    //类似后序遍历
    Node lc = dfs(root * 2), rc = dfs(root * 2 + 1);
    return rt = lc.v_ > rc.v_ ? lc : rc;//每次取左右孩子的最大值建立父结点
}

int main()
{
    cin >> N;
    //顺序存储树时，1为根结点下标
    //2 * i为左孩子下标，2 * i + 1为右孩子下标
    //先填满叶子结点，满二叉树中，编号不小于1 << N都是叶子结点
    for (int i = 0; i < (1 << N); ++i)
    {
        cin >> arr[i + (1 << N)].v_;
        arr[i + (1 << N)].id_ = i + 1;
    }
    dfs(1);
    cout << (arr[2].v_ < arr[3].v_ ? arr[2].id_ : arr[3].id_);
    return 0;
}

思路

根据题意画出如下流程图

很显然题目是要我们根据叶子结点构造一颗满二叉树，以父结点等于两个子结点中的最大值这个规律