給一棵笛卡兒樹的中序遍歷，輸出其前序遍歷。
笛卡兒樹: 一棵滿足任意節點權重皆小於其所有子節點的樹。
$N\le 10^4, 1\le a_i \le 10^9, a_i \ne a_j(i\ne j)$
首先要知道：笛卡兒樹是一個根據數列蓋出來的樹，而其中序遍歷會剛好還原出原本的數列，所以問題就變成：給一個數列，輸出其特定的笛卡兒樹的前序遍歷。
然後再知道：中序遍歷中，對於任意點其左子樹都會在該點左邊，右子樹會在該點右邊。
這樣就有一個解法了：每次找出最小的元素(根節點)，輸出他(前序遍歷)，然後再分別遞迴左右半邊(左子樹&右子樹)，一路遞迴到沒東西為止。
複雜度的部分：因為每次都會花$\mathcal{O}(n)$時間找出最小的元素，且會遞迴$\mathcal{O}(logn)$層，所以複雜度是$\mathcal{O}(nlogn)$。
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
39
40
41
42
43
44
45
46
47
48
49
|
#include <bits/stdc++.h>
using namespace std;
#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(NULL);
#define mem(i,j) memset(i,j,sizeof (i));
using ll = int64_t;
using ull = uint64_t;
using ld = long double;
using uint = uint32_t;
const double EPS = 1e-8;
const int INF = 0x3F3F3F3F;
const ll LINF = 4611686018427387903;
const int MOD = 1e9+7;
void solve(int l, int r, vector<int> &arr) {
if(l >= r)
return;
int w = min_element(arr.begin() + l, arr.begin() + r) - arr.begin();
cout << arr[w] << ' ';
solve(l, w, arr);
solve(w + 1, r, arr);
}
signed main() {
EmiliaMyWife
int n;
while(cin >> n, n) {
vector<int> arr(n);
for(int i = 0; i < n; i++)
cin >> arr[i];
solve(0, n, arr);
cout << '\n';
}
return 0;
}
|