題目連結
https://codeforces.com/problemset/problem/1741/D
題目概要
給你一個 \(1; 2 …m\) 但沒有排序的數列，其中 \(m=2^n, n \in N\)。 這些數字要被放在一個完全二元樹的樹葉(葉節點)中。 定義此完全二元樹是 “\(beautiful\)” 的若且唯若葉節點的數值剛好由左而右遞增。 我們可以做的操作是對任一節點，將他的左右子樹互換。 請問最少幾次操作可以讓樹變成 “\(beautiful\)” 的，如果做不到輸出 -1。
提示 1
判斷做不做得到與怎麼做可以分開。
提示 2
怎麼做可以快速分辨是否成功。想想線段樹。
想法
仿造線段樹的作法，我們可以直接建立一顆完全二元樹，也可以用線段樹取代。我使用指標實作完全二元樹，在每個節點中增加一個數mn表示這棵子樹的所有節點的最小值。如果左子樹的最小值大於右子樹的最小值，則樹就需要旋轉(交換左右子樹)。
而分辨能否成功則可以用左右子樹最小值的差，如果可以成功旋轉，則所有節點的左右子樹最小值差一定要是 \(2^{該節點的高度-1}\)。而顯然滿足這條件就可以成功藉由有限次操作使樹變得 “\(beautiful\)”。
程式碼
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
| #include<bits/stdc++.h>
using namespace std;
int INF=0x3f3f3f3f;
struct binary_tree{
struct node{
node *lch,*rch;
int mn=INF,val=0;
node(){
lch=rch=nullptr;
}
void swap_subtree(){
swap(lch,rch);
}
};
node *rt=new node();
int idx=0,h=0;
int test(node *n,int hi){
if(!n->lch){
return 0;
}
if(abs(n->lch->mn - n->rch->mn)!=1<<(hi-2)){
return -1;
}
int ret=0;
if(n->lch->mn > n->rch->mn){
ret++;
n->swap_subtree();
}
int ls=test(n->lch,hi-1),rs=test(n->rch,hi-1);
if(ls==-1 || rs==-1){
return -1;
}
ret+=ls+rs;
return ret;
}
int test(){
return test(rt,h);
}
void build(int h,node *n,vector<int> &v){
if(h<=1){
n->mn=n->val=v[idx];
idx++;
return;
}
n->lch=new node();
n->rch=new node();
build(h-1,n->lch,v);
build(h-1,n->rch,v);
if(n->lch && n->rch){
n->mn=min(n->lch->mn,n->rch->mn);
}
}
binary_tree(vector<int> v){
int n=v.size();
while(n>0){
h++; n>>=1;
}
build(h,rt,v);
}
void delete_tree(node *n){
if(!n) return;
if(n->lch) delete_tree(n->lch);
if(n->rch) delete_tree(n->rch);
delete(n);
}
~binary_tree(){
delete_tree(rt);
}
};
void solve(){
int m;
cin>>m;
vector<int> v(m);
for(auto &i:v) cin>>i;
binary_tree cbt(v);
cout<<cbt.test()<<"\n";
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);
int t=1;
cin>>t;
while(t--){
solve();
}
}
|