【題目敘述】https://judge.tcirc.tw/ShowProblem?problemid=d105 (n <= 1e5)
【題目敘述】https://zerojudge.tw/ShowProblem?problemid=f163 (n <= 1e6)
【解題想法】陣列應用, BST (binary search tree)
【做法1】陣列應用 (ZeroJudge: AC, TCIRC: AC）
#include <iostream>
#include <vector>
using namespace std;
const int maxn = 1000005;
int n, m, l[maxn], r[maxn], p[maxn*2], tot[maxn*2];
vector <int> v;
void build(int x){
if (x >= n) return;
build(l[x]);
build(r[x]);
tot[x] = tot[l[x]] + tot[r[x]];
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i = n; i < n*2; i++){
cin >> tot[i];
}
for (int i = 0; i < m; i++){
int q;
cin >> q;
v.push_back(q);
}
for (int i = 1; i < n; i++){
int x, y, z;
cin >> x >> y >> z;
l[x] = y;
r[x] = z;
p[y] = x;
p[z] = x;
}
int root = 0;
for (int i = 1; i < n; i++){
if (!p[i]){
root = i;
break;
}
}
build(root);
for (int i:v){
int now = root;
while (now < n){
if (tot[l[now]] <= tot[r[now]]){
tot[l[now]] += i;
now = l[now];
}
else{
tot[r[now]] += i;
now = r[now];
}
}
cout << now << " ";
}
}
【做法2】BST (ZeroJudge: AC, TCIRC: TLE)
- w[ ]：紀錄每個貨櫃裝載的貨物總重量
- p[ ]：紀錄每個節點的parent (父節點)
- L[ ]：紀錄每個節點的left child (左兒子)
- R[ ]：紀錄每個節點的right child (右兒子)
- 函式 pull( )：每次裝載新的貨物後，從該貨櫃往上回溯所有父節點，一路更新每個節點的重量。
- 每次分裝新貨物時，比較左右兒子的負載，決定接下來往哪一個分裝站或貨櫃移動，直到遇到貨櫃為止。
#include <iostream>
using namespace std;
const int maxn = 1000001;
//n個貨櫃與n-1個分裝站, n≤1,000,000
//給這2n-1個節點各自一個編號 (從1開始, 第n到第2n-1為貨櫃)
int n, m;
int w[2*maxn]; //weight
int p[2*maxn]; //parent
int L[2*maxn]; //left child
int R[2*maxn]; //right child
int obj[10005]; //1≤m≤10,000
void pull(int i, int delta){
while (p[i] != 0){
w[p[i]] += delta;
i = p[i];
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int a, b, c;
cin >> n >> m;
for (int i=n; i<2*n; i++){
cin >> w[i];
}
for (int i=0; i<m; i++){
cin >> obj[i];
}
for (int i=0; i<n-1; i++){
cin >> a >> b >> c;
L[a] = b;
R[a] = c;
p[b] = a;
p[c] = a;
}
for (int i=n; i<2*n; i++){
pull(i, w[i]);
}
int ans[m];
for (int i=0; i<m; i++){
//依序進入這個自動分裝系統, 必定由1號分裝站開始
int now = 1;
while (now < n){
int left = L[now];
int right = R[now];
if (w[left] <= w[right]){
now = left;
} else {
now = right;
}
}
w[now] += obj[i];
pull(now, obj[i]);
ans[i] = now;
}
cout << ans[0];
for (int i=1; i<m; i++){
cout << ' ' << ans[i];
}
cout << '\n';
return 0;
}