# APCS實作題2020年1月第4題：貨物分配

> 第1版：2024年7月9日
> 第2版：2025年1月14日，加上吳邦一教授的寫法
> 作者：王一哲
> 題目來源：2020年1月實作題第4題
> [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=f163)

## 題目

### 問題描述

在一個貨運站有一個自動分裝系統，在系統中有 $n-1$ 個分裝站（編號 $1$ 到 $n-1$） 和 $n$ 個貨櫃（編號 $n$ 到 $2n-1$），也就是總共有 $2n-1$ 個節點。對於每個分裝站，都會有左右兩個分支前往下個分裝站或貨櫃。

以下圖 $n = 7$ 的範例輸入1為例，圓形為分裝站，方形為貨櫃：

<img height="60%" width="60%" src="https://imgur.com/ubkIGWw.png" style="display: block; margin-left: auto; margin-right: auto;"/>
<div style="text-align:center">範例輸入1示意圖，下方的5邊形是每個貨櫃原來的重量，菱形是放入的貨物重量。</div><br /><br />

給定 $m$ 個不同重量的貨物（$1 \leq m \leq 10^4$），要依序進入這個自動分裝系統以裝進貨櫃裡，分裝規則如下：

1. 每個貨物必定由 $1$ 號分裝站開始
2. 對於每個分裝站，都會比較當下左右兩邊分支的貨物總重，之後選擇進入總重較輕的那一邊。
3. 若左右兩邊重量相等，則選擇左邊的分裝站。
4. 直到貨物進到貨櫃（方形處）。

注意：貨物一旦放入貨櫃中，會影響到後續貨物進來時的走向，並且所有貨物的總重和不超過 $10^9$。

假設每個貨櫃事先都包含了若干貨物重量，請計算這 $m$ 個貨物依序會被放入哪個貨櫃中。
<br />

### 輸入說明

第一行包含兩個數字 $n, m ~(1 \leq n \leq 10^6,~ 1 \leq m \leq 10^4)$，代表一共有 $n$ 個貨櫃與 $m$ 個準備要放入系統中的貨物。

第二行有 $n$ 個數字，代表第 $n \sim 2n−1$ 個貨櫃在開始分裝系統開始前已有的貨物重量。

第三行包含 $m$ 個數字，代表即將放入的 $m$ 個貨物的重量。

最後有 $n-1$ 行，每行有三個數字 $a, b, c$，分別代表 $a$ 左邊的分裝站為 $b$，$a$ 右邊的分裝站為 $c$。

所有貨物，包含已有與後來放入的 $m$ 個貨物的總重和不超過 $10^9$。

<br />

### 輸出格式

輸出這 $m$ 個貨物被放入的貨櫃編號，數字之間兩兩以空白為間隔。

<br />

### 範例輸入1

7 2
9 2 1 6 7 4 5
2 3
1 2 5
2 3 7
3 13 10
4 9 11
6 12 8
5 6 4

### 範例輸出1

8 12

### 範例輸入2

4 5
0 0 0 0
5 3 4 2 1
1 2 3
2 4 5
3 6 7

### 範例輸出2

4 6 7 5 5

<br />

<img height="45%" width="45%" src="https://imgur.com/ygLuF3f.png" style="display: block; margin-left: auto; margin-right: auto;"/>
<div style="text-align:center">範例輸入2示意圖，下方的5邊形是每個貨櫃原來的重量，菱形是放入的貨物重量。</div><br /><br />

## Python 程式碼

### 寫法1，使用 list 儲存資料

程式邏輯無誤，但是最後5筆測資太大，在第2行或第4行使用 input().split() 讀取整行的測資時記憶體會爆掉。

n, m = map(int, input().split())  # 讀取 n、貨物數量 m
ws = list(map(int, input().split()))  # 讀取每個貨櫃初始重量 ws
mass = list(map(int, input().split()))  # 讀取 m 個貨物的重量 mass
sites = [[0, 0, 0] for _ in range(n+n)]  # index 為貨運站或貨櫃編號，0是空號，對應的值依序為左、右、總重
for _ in range(n-1):  # 讀取 n-1 行資料
    root, left, right = map(int, input().split())  # 讀取貨運站或貨櫃編號 root，左側編號 left，右側編號 right
    sites[root] = [left, right, 0]  # 先建立貨運站、貨櫃關係圖，總重量先預設為0
for i, w in enumerate(ws, start=n):  # 依序讀取 ws，編號從 n 開始
    sites[i] = [0, 0, w]  # 填入貨櫃的初始重量，left = 0, right = 0

""" 自訂函式：初始化各貨運站的總重量 """
def init(idx):
    if idx >= n: return sites[idx][2]  # 這是貨櫃，回傳貨櫃重量
    sites[idx][2] = init(sites[idx][0]) + init(sites[idx][1])  # 這是貨運站，遞回，代入對應的 left 及 right
    return sites[idx][2]  # 回傳這個貨運站的總重量
""" end init """
init(1)  # 呼叫 init，idx 由 1 開始

ans = []  # 儲存答案用的串列
""" 自訂函式：主要的解題過程，放入貨物 """
def solve(ms, idx):  # 代入貨物重量 ms、貨運站或貨櫃編號 idx
    sites[idx][2] += ms  # 更新編號 idx 的重量
    if idx >= n:  # 這是貨櫃
        ans.append(idx)  # 將 idx 加入 ans
        return  # 跳出 solve
    if sites[sites[idx][0]][2] <= sites[sites[idx][1]][2]:  # 如果 idx 的左側重量小於等於右側重量
        solve(ms, sites[idx][0])  # 遞迴，代入 ms 及左側編號
    else:  # 如果 idx 的左側重量大於右側重量
        solve(ms, sites[idx][1])  # 遞迴，代入 ms 及右側編號
""" end solve """

for ms in mass: solve(ms, 1)  # 依序代入每個貨物的重量 ms，呼叫 solve 時，編號都從1開始
print(*ans)  # 印出答案

<br /><br />

### 寫法2，使用 array 並限制每次用 split 分割的資料筆數

第49筆測資費時 5s、使用記憶體 49.8MB。剩下第48筆測資無法通過，應該是使用了太多記憶體，回傳的錯誤訊息為

您的程式被監控系統中斷，可能是程式無法正常結束所導致。
Traceback (most recent call last):
  File "/14214852_f163/code_14214852.py", line 35, in 
    weight = array('i', [0]*(n+n))  # 索引值為 index 對應的重量樹
MemoryError

from array import array
import gc

n, m = map(int, input().split())  # 讀取 n、貨物數量 m
ws = array('i')  # 每個貨櫃初始重量 ws
mass = array('i')  # m 個貨物的重量 mass
line = input()  # 讀取一行資料
while line:  # 如果 line 還有資料時繼續執行
    tmp = list(line.split(maxsplit=100))  # 每次最多分割 100 筆資料
    num = sum(len(t)+1 for t in tmp[:100])  # 計算已分割的資料長度，每次都要加1格空格
    ws += array('i', map(int, tmp[:100]))  # 將已分割的資料轉成 int 加入 ws
    line = line[num:]  # 切掉已分割的資料

line = input()  # 讀取一行資料
while line:  # 如果 line 還有資料時繼續執行
    tmp = list(line.split(maxsplit=100))  # 每次最多分割 100 筆資料
    num = sum(len(t)+1 for t in tmp[:100])  # 計算已分割的資料長度，每次都要加1格空格
    mass += array('i', map(int, tmp[:100]))  # 將已分割的資料轉成 int 加入 mass
    line = line[num:]  # 切掉已分割的資料

del line  # 刪除 line
del tmp  # 刪除 tmp
gc.collect()  # 回收垃圾

left = array('i', [0]*n)  # 索引值為 index 對應的左子樹，貨櫃沒有左子樹
right = array('i', [0]*n)  # 索引值為 index 對應的右子樹，貨櫃沒有右子樹
weight = array('i', [0]*(n+n))  # 索引值為 index 對應的重量樹
for _ in range(n-1):  # 讀取 n-1 行資料
    idx, le, ri = map(int, input().split())  # 讀取貨運站或貨櫃編號 idx，左側編號 le，右側編號 ri
    left[idx] = le; right[idx] = ri  # 先建立貨運站、貨櫃關係圖，總重量先預設為0
for i in range(n): weight[n+i] = ws[i] # 填入貨櫃的初始重量

""" 自訂函式：初始化各貨運站的總重量 """
def init(idx):
    if idx >= n: return weight[idx]  # 這是貨櫃，回傳貨櫃重量
    weight[idx] = init(left[idx]) + init(right[idx])  # 這是貨運站，遞回，代入對應的 left 及 right
    return weight[idx]  # 回傳這個貨運站的總重量
""" end init """
init(1)  # 呼叫 init，idx 由 1 開始

ans = []  # 儲存答案用的串列
""" 自訂函式：主要的解題過程，放入貨物 """
def solve(ms, idx):  # 代入貨物重量 ms、貨運站或貨櫃編號 idx
    weight[idx] += ms  # 更新編號 idx 的重量
    if idx >= n:  # 這是貨櫃
        ans.append(idx)  # 將 idx 加入 ans
        return  # 跳出 solve
    if weight[left[idx]] <= weight[right[idx]]:  # 如果 idx 的左側重量小於等於右側重量
        solve(ms, left[idx])  # 遞迴，代入 ms 及左側編號
    else:  # 如果 idx 的左側重量大於右側重量
        solve(ms, right[idx])  # 遞迴，代入 ms 及右側編號
""" end solve """

for ms in mass: solve(ms, 1)  # 依序代入每個貨物的重量 ms，呼叫 solve 時，編號都從1開始
print(*ans)  # 印出答案

<br /><br />

### 寫法3，吳邦一教授的寫法，bottom-up

改用 deque 儲存待走訪節點，但在 ZeroJudge 第 46 筆測資超時。

from collections import deque

n, m = map(int, input().split())  # n-1 個切換器，n 個貨箱，m 個貨物
w = [0]*n + list(map(int, input().split()))  # 貨箱初始重量，編號為 n ~ 2n-1
seq = list(map(int, input().split()))  # 依序放入的貨物重量
lc, rc = [-1]*(2*n), [-1]*(2*n)  # 左、右子節點編號
parent = [0]*(2*n)  # 父節點編號
for _ in range(n-1):  # 讀取 n-1 行貨架資訊
    p, s, t = map(int, input().split())  # 切換器 p，左側接到 s，右側接到 t
    lc[p] = s; rc[p] = t  # 儲存子節點編號
    parent[s] = parent[t] = p  # s、t 的父節點皆為 p
# 初始化，找每個節點的總重量
deg = [2]*n  # 切換器的子節點數量，原來都有 2 個
que = deque(list(range(n, 2*n)))  # 待走訪佇列，從葉節點開始，編號為 n ~ 2n-1
while que:  # 若 que 還有資料繼續執行
    v = que.popleft()  # 從 que 最前面讀取並移除節點 v
    if v == 1: break  # v 是根節點，中止迴圈
    u = parent[v]  # v 的父節點 u
    w[u] += w[v]  # 更新 u 的總重量，加上 v 的總重量
    deg[u] -= 1  # u 的子節點數量減 1
    if deg[u] == 0: que.append(u)  # 如果 u 沒有子節點了，加入 que
# 模擬貨物分配的過程
for i, wi in enumerate(seq):  # 依序讀取貨物重量
    v = 1  # 從 1 號切換器開始
    while v < n:  # 還在切換器範圍內
        if w[lc[v]] <= w[rc[v]]:  # 如果左節點總重量小於等於右節點總重量
            v = lc[v]  # 放到左節點
        else: v = rc[v]  # 反之，放到右節點
        w[v] += wi  # 更新 v 的總重量
    # end of while loop 進到貨箱，印出貨箱編號
    print(v, end="\n" if i == m-1 else " ")

<br /><br />

## C++ 程式碼

### 寫法1，二維 vector

用二維 vector 儲存各貨運站、貨櫃的左、右、重量，但是這樣會使用太多記憶體，在最後3筆測資會遇到 RE (SIGABRT)。

#include <iostream>
#include <vector>
using namespace std;

/* 自訂函式：初始化各貨運站的總重量 */
int init(vector<vector<int>>& sites, int idx, int n) {
    if (idx >= n) return sites[idx][2];  // 這是貨櫃，回傳貨櫃重量
    sites[idx][2] = init(sites, sites[idx][0], n) + init(sites, sites[idx][1], n);  // 這是貨運站，遞回，代入對應的 left 及 right
    return sites[idx][2];  // 回傳這個貨運站的總重量
}

/* 自訂函式：主要的解題過程，放入貨物 */
void solve(vector<vector<int>>& sites, vector<int>& ans, int ms, int idx, int n) {  // 代入貨物重量 ms、貨運站或貨櫃編號 idx
    sites[idx][2] += ms;  // 更新編號 idx 的重量
    if (idx >= n) {  // 這是貨櫃
        ans.push_back(idx);  // 將 idx 加入 ans
        return;  // 跳出 solve
    }
    // 如果 idx 的左側重量小於等於右側重量，遞迴，代入 ms 及左側編號
    // 反之，代入 ms 及右側編號
    if (sites[sites[idx][0]][2] <= sites[sites[idx][1]][2]) solve(sites, ans, ms, sites[idx][0], n);
    else solve(sites, ans, ms, sites[idx][1], n);
    return;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);  // 加快輸入、輸出
    int n, m; cin >> n >> m;  // 讀取 n、貨物數量 m
    vector<vector<int>> sites (n+n, vector<int> (3, 0));  // index 為貨運站或貨櫃編號，0是空號，對應的值依序為左、右、總重
    for(int i=0; i<n; i++) cin >> sites[n+i][2];  // 讀取每個貨櫃初始重量 ws
    vector<int> mass (m, 0);  // m 個貨物的重量 mass
    for(int i=0; i<m; i++) cin >> mass[i];  // 讀取 m 個貨物的重量 mass
    for(int i=0; i<n-1; i++) {  // 先建立貨運站、貨櫃關係圖，總重量先預設為0
        int a, b, c; cin >> a >> b >> c;
        sites[a] = {b, c, 0};
    }
    init(sites, 1, n);  // 呼叫 init，idx 由 1 開始
    
    vector<int> ans;  // 答案
    for(int ms : mass) solve(sites, ans, ms, 1, n);  // 依序代入每個貨物的重量 ms，呼叫 solve 時，編號都從1開始
    //for(auto site : sites) cout << site[0] << " " << site[1] << " " << site[2] << "\n";
    for(int i=0; i<m; i++) cout << ans[i] << " \n"[i == m-1];  // 印出答案  
    
    return 0;
}

<br /><br />

### 寫法2，只使用一維 vector

將寫法1的 sites 拆成 3 個一維 vector，分別為儲存左子樹的 left，儲存右子樹的 right，儲存重量的 weight。費時最久約為 0.6 s，使用記憶體最多約為 14.2 MB，通過測試。

#include <iostream>
#include <vector>
using namespace std;

/* 自訂函式：初始化各貨運站的總重量 */
int init(vector<int>& left, vector<int>& right, vector<int>& weight, int idx, int n) {
    if (idx >= n) return weight[idx];  // 這是貨櫃，回傳貨櫃重量
    weight[idx] = init(left, right, weight, left[idx], n) + init(left, right, weight, right[idx], n);  // 這是貨運站，遞回，代入對應的 left 及 right
    return weight[idx];  // 回傳這個貨運站的總重量
}

/* 自訂函式：主要的解題過程，放入貨物 */
void solve(vector<int>& left, vector<int>& right, vector<int>& weight, vector<int>& ans, int ms, int idx, int n) {
    weight[idx] += ms;  // 更新編號 idx 的重量
    if (idx >= n) {  // 這是貨櫃
        ans.push_back(idx);  // 將 idx 加入 ans
        return;  // 跳出 solve
    }
    // 如果 idx 的左側重量小於等於右側重量，遞迴，代入 ms 及左側編號
    // 反之，代入 ms 及右側編號
    if (weight[left[idx]] <= weight[right[idx]]) solve(left, right, weight, ans, ms, left[idx], n);
    else solve(left, right, weight, ans, ms, right[idx], n);
    return;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);  // 加快輸入、輸出
    int n, m; cin >> n >> m;  // 讀取 n、貨物數量 m
    vector<int> left (n, 0), right (n, 0), weight (n+n, 0), mass (m, 0);
    for(int i=0; i<n; i++) cin >> weight[n+i];  // 讀取每個貨櫃初始重量 ws
    for(int i=0; i<m; i++) cin >> mass[i];  // 讀取 m 個貨物的重量 mass
    for(int i=0; i<n-1; i++) {  // 先建立貨運站、貨櫃關係圖，總重量先預設為0
        int a, b, c; cin >> a >> b >> c;
        left[a] = b; right[a] = c;
    }
    init(left, right, weight, 1, n);  // 呼叫 init，idx 由 1 開始
    
    vector<int> ans;  // 答案
    for(int ms : mass) solve(left, right, weight, ans, ms, 1, n);  // 依序代入每個貨物的重量 ms，呼叫 solve 時，編號都從1開始
    for(int i=0; i<m; i++) cout << ans[i] << " \n"[i == m-1];  // 印出答案    
    
    return 0;
}

<br /><br />

### 寫法3，吳邦一教授的寫法，bottom-up

費時最久約為 0.6 s，使用記憶體最多約為 35.1 MB，通過測試。

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m; cin >> n >> m;  // n-1 個切換器，n 個貨箱，m 個貨物
    vector<int> w (2*n, 0);  // 切換器、貨箱重量，數量有 2n-1 個
    for(int i=n; i<2*n; i++) cin >> w[i];  // 讀取貨箱初始重量，編號為 n ~ 2n-1
    vector<int> seq (m, 0);  // 放入的貨物重量
    for(int i=0; i<m; i++) cin >> seq[i];
    vector<int> lc (2*n, -1), rc (2*n, -1), parent (2*n, 0);  // 左節點，右節點，父節點
    for(int i=1, p, s, t; i<n; i++) {  // 讀取 n-1 行資料
        cin >> p >> s >> t;  // 切換器 p，左節點 s，右節點 t
        lc[p] = s; rc[p] = t;  // p 的左節點為 s，右節點為 t
        parent[s] = p; parent[t] = p;  // s、t 的父節點為 p
    }
    /* 初始化，找每個切換器、貨箱總重量 */
    vector<int> deg (n, 2);  // 切換器子節點數量，原來都是 2
    queue<int> que;  // 待走訪節點，從葉節點開始
    for(int i=n; i<2*n; i++) que.push(i);
    while(!que.empty()) {  // 如果 que 還有資料繼續執行
        int v = que.front(); que.pop();  // 從 que 最前面讀取並移除資料
        if (v == 1) break;  // v 是根節點，中止迴圈
        int u = parent[v];  // v 的父節點為 u
        w[u] += w[v];  // u 的總重量要加上 v 的總重量
        deg[u]--;  // u 的子節點數量減 1
        if (deg[u] == 0) que.push(u);  // 如果 u 沒有子節點，加入 que
    }
    /* 模擬貨物分配過程 */
    for(int i=0; i<m; i++) {
        int wi = seq[i], v = 1;  // 依序讀取貨物重量 wi，從 1 號切換器開始
        while(v < n) {  // 還在切換器範圍內
            if (w[lc[v]] <= w[rc[v]]) v = lc[v];  // 如果 v 的左節點總重量小於等於右節點總重量，放到左子節點
            else v = rc[v];  // 反之，放到右節點
            w[v] += wi;  // 更新 v 的總重量
        }
        cout << v << " \n"[i == m-1];  // 印出貨箱編號，如果是最後一項要換行
    }
    return 0;
}

<br /><br />

---

###### tags:`APCS`、`Python`、`C++`