# APCS實作題2020年1月第4題:貨物分配
> 日期:2024年7月9日
> 作者:王一哲
> 題目來源: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() 讀取整行的測資時記憶體會爆掉。
```python=
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筆測資無法通過,應該是使用了太多記憶體,回傳的錯誤訊息為
```python
您的程式被監控系統中斷,可能是程式無法正常結束所導致。
Traceback (most recent call last):
File "/14214852_f163/code_14214852.py", line 35, in
weight = array('i', [0]*(n+n)) # 索引值為 index 對應的重量樹
MemoryError
```
```python=
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 />
## C++ 程式碼
### 寫法1,二維 vector
用二維 vector 儲存各貨運站、貨櫃的左、右、重量,但是這樣會使用太多記憶體,在最後3筆測資會遇到 RE (SIGABRT)。
```cpp=
#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,通過測試。
```cpp=
#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;
}
```
---
###### tags:`APCS`、`Python`、`C++`