f163: 貨物分配
Tags :
Accepted rate : 65人/85人 ( 76% ) [非即時]
評分方式:
Tolerant

最近更新 : 2020-07-24 06:49

Content

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

以下圖 n = 7 為例,圓形為分裝站,方形為貨櫃:


給定 m 個不同重量的貨物(1 ≤ m ≤ 104),要依序進入這個自動分裝系統以裝進貨櫃裡,分裝規則如下:

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

注意:貨物一旦放入貨櫃中,會影響到後續貨物進來時的走向,並且所有貨物的總重和不超過 109

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

 

Input

第一行包含兩個數字 n, m(1 ≤ n ≤ 106, 1 ≤ m ≤ 104),
代表一共有 n 個貨櫃與 m 個準備要放入系統中的貨物

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

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

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

所有貨物,包含已有與後來放入的 m 個貨物的總重和不超過 109

 

Output

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

Sample Input #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
Sample Output #1
8 12
Sample Input #2
4 5
0 0 0 0
5 3 4 2 1
1 2 3
2 4 5
3 6 7
Sample Output #2
4 6 7 5 5
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (2%): 1.0s , <1K
公開 測資點#1 (2%): 1.0s , <1K
公開 測資點#2 (2%): 1.0s , <1K
公開 測資點#3 (2%): 1.0s , <1K
公開 測資點#4 (2%): 1.0s , <1K
公開 測資點#5 (2%): 1.0s , <1M
公開 測資點#6 (2%): 1.0s , <1K
公開 測資點#7 (2%): 1.0s , <1M
公開 測資點#8 (2%): 1.0s , <1M
公開 測資點#9 (2%): 1.0s , <1M
公開 測資點#10 (2%): 1.0s , <1M
公開 測資點#11 (2%): 1.0s , <1M
公開 測資點#12 (2%): 1.0s , <1K
公開 測資點#13 (2%): 1.0s , <1M
公開 測資點#14 (2%): 1.0s , <1M
公開 測資點#15 (2%): 1.0s , <1M
公開 測資點#16 (2%): 1.0s , <1M
公開 測資點#17 (2%): 1.0s , <1M
公開 測資點#18 (2%): 1.0s , <1M
公開 測資點#19 (2%): 1.0s , <1M
公開 測資點#20 (2%): 1.0s , <1M
公開 測資點#21 (2%): 1.0s , <1M
公開 測資點#22 (2%): 1.0s , <1M
公開 測資點#23 (2%): 1.0s , <1M
公開 測資點#24 (2%): 1.0s , <1M
公開 測資點#25 (2%): 1.0s , <1M
公開 測資點#26 (2%): 1.0s , <1M
公開 測資點#27 (2%): 1.0s , <1M
公開 測資點#28 (2%): 1.0s , <1M
公開 測資點#29 (2%): 1.0s , <1M
公開 測資點#30 (2%): 1.0s , <1M
公開 測資點#31 (2%): 1.0s , <1M
公開 測資點#32 (2%): 1.0s , <1M
公開 測資點#33 (2%): 1.0s , <1M
公開 測資點#34 (2%): 1.0s , <1M
公開 測資點#35 (2%): 1.0s , <10M
公開 測資點#36 (2%): 1.0s , <10M
公開 測資點#37 (2%): 1.0s , <10M
公開 測資點#38 (2%): 1.0s , <1M
公開 測資點#39 (2%): 1.0s , <10M
公開 測資點#40 (2%): 1.0s , <10M
公開 測資點#41 (2%): 1.0s , <10M
公開 測資點#42 (2%): 1.0s , <1M
公開 測資點#43 (2%): 1.0s , <1M
公開 測資點#44 (2%): 1.0s , <1M
公開 測資點#45 (2%): 1.0s , <10M
公開 測資點#46 (2%): 1.0s , <10M
公開 測資點#47 (2%): 2.0s , <50M
公開 測資點#48 (2%): 2.0s , <50M
公開 測資點#49 (2%): 2.0s , <50M
Hint :
Tags:
出處:
APCS2020年1月 [管理者:
mushroom.cs9... (mushroom)
]


ID User Problem Subject Hit Post Date
24596
fire5386 (fffelix)
f163
陣列大小
307 2021-03-08 22:25
24589
jam930725@gm... (浮沉沉沉沉沉沉沉沉)
f163
JAVA 避免MLE
239 2021-03-07 22:04
24558
fire5386 (fffelix)
f163
優化
309 2021-03-04 20:02