回『IOI/APCS』
f163. 貨物分配
標籤 :
通過比率 : 232人/336人 ( 69% ) [非即時]
評分方式：
Tolerant

最近更新 : 2021-10-27 01:39

內容

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

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


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

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

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

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

 

輸入說明

第一行包含兩個數字 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

 

輸出說明

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

範例輸入 #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
測資資訊：
記憶體限制： 512 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
提示 ：
標籤:
出處:
2020年1月APCS [管理者： mushroom.cs9 ... (mushroom) ]

本題狀況 本題討論 排行

編號 身分 題目 主題 人氣 發表日期
37264 fire5386 (becaidorz) f163
解題想法
350 2023-08-29 00:36
34925 luray0601@gm ... (QWERTYPIG) f163
C++題解(含想法)
430 2023-04-27 08:39
31124 abcd950813 (H.) f163
593 2022-07-13 11:58
27441 r1cky (hehe) f163
Java 解題心得
697 2021-10-06 14:26
24596 fire5386 (becaidorz) f163
陣列大小
1196 2021-03-08 22:25