f163 - 貨物分配
題目描述
題目描述了一個貨物分配系統，其中有分裝站和貨櫃。貨物從 1 號分裝站進入，根據左右分支的貨物總重選擇較輕的一方，直到進入貨櫃。題目要求計算 m 個貨物依序進入系統後，會被放入哪個貨櫃中。
解題思路
這題的核心是模擬貨物在分裝系統中的流動過程。系統可以視為一個二元樹，其中分裝站是節點，貨櫃是葉子節點。對於每個貨物，我們從根節點（1 號分裝站）開始，根據貪心策略（選擇較輕的分支）向下移動，直到到達一個葉子節點（貨櫃）。每次貨物進入貨櫃後，需要更新該貨櫃的重量，以便影響後續貨物的流動方向。
程式碼使用了一個 node 結構體來表示分裝站，包含指向左子節點、右子節點以及左右分支的貨物總重的成員。cal 函數用於計算整個樹的貨物總重（雖然在本題中並未直接使用到，但可以作為一個輔助函數）。Dis 函數模擬貨物在樹中的移動過程，並返回貨物最終進入的貨櫃的編號。main 函數讀取輸入數據，構建二元樹，然後依次處理每個貨物，輸出其進入的貨櫃編號。
複雜度分析
- 時間複雜度: O(m * n)，其中 m 是貨物數量，n 是貨櫃數量。對於每個貨物，最壞情況下需要遍歷樹的高度，而樹的高度最壞情況下為 n。
- 空間複雜度: O(n)，主要用於存儲二元樹的節點。
程式碼
#include <iostream>
using namespace std;
int b[10001],n,m,it,lit,rit;
struct node {
node *left = nullptr, *right = nullptr;
int lw = 0, rw = 0;
} s[2000001];
int cal(node *tmp) {
if (!tmp->left && !tmp->right)
return tmp->lw;
tmp -> lw = cal(tmp->left);
tmp -> rw = cal(tmp->right);
return tmp->lw+tmp->rw;
}
int Dis(int w, node *tmp) {
while (tmp->left||tmp->right) {
if (tmp->lw <= tmp->rw) {
tmp->lw += w;
tmp = tmp->left;
}
else {
tmp->rw += w;
tmp = tmp->right;
}
}
return (tmp-s);
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
cin >> n >> m;
for(int i=n;i<n*2;++i){
cin >> s[i].lw;
}
for(int i=0;i<m;++i){
cin >> b[i];
}
for(int i=1;i<n;++i){
cin >> it >> lit >> rit;
s[it].left = &s[lit];
s[it].right = &s[rit];
}
cal(&s[1]);
for (int i=0;i<m;++i)
cout << Dis(b[i], &s[1]) << ' ';
}