【洛谷】AT_abc188_c [ABC188C] ABC Tournament 的题解

【洛谷】AT_abc188_c [ABC188C] ABC Tournament 的题解

洛谷传送门

AT传送门

Vjudge传送门

题解

谔谔，最近月考，没时间写题解。现在终于有时间了qaq

通过对样例的数据分析我们可以看到。本题的考点就是一个二叉搜索树，因此最简单的方法就是使用递归来实现。

我们将当前节点编号为 $i$，其父节点编号为 $\frac{i}{2}$，其右兄弟节点编号为 $i+1$。

这样，我们通过控制数组下标，即可实现。时间复杂度 $O(\log 2^N)$

代码

#include <bits/stdc++.h>
#define lowbit(x) x & (-x)
#define endl "\n"
using namespace std;
typedef long long ll;
typedef unsigned long long ulson;
namespace fastIO {
	inline int read() {
		register int x = 0, f = 1;
		register char c = getchar();
		while (c < '0' || c > '9') {
			if(c == '-') f = -1;
			c = getchar();
		}
		while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
		return x * f;
	}
	inline void write(int x) {
		if(x < 0) putchar('-'), x = -x;
		if(x > 9) write(x / 10);
		putchar(x % 10 + '0');
		return;
	}
}
using namespace fastIO;
int a[100005], n;
int dfs(int l, int r) {
    if (l + 1 == r) {
        return a[l] > a[r] ? l : r;
    }
    int mid = (l + r) >> 1;
    int lson = dfs(l, mid), rson = dfs(mid + 1, r);
    if(l == 1 && r == n) {
        cout << (a[lson] > a[rson] ? rson : lson) << endl;
        return 0;
    } 
	else {
        return a[lson] > a[rson] ? lson : rson;
    }
}
int main() {
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
	n = read();
    n = 1 << n;
    for(int i = 1; i <= n; i ++) {
        a[i] = read();
    }
    if(n == 2) {
        cout << (a[1] > a[2] ? "2" : "1") << endl;
    }
    else {
    	dfs(1, n);
	}
	return 0;
}