主題

ZeroJudge - f163: 貨物分配 解題心得

Not In My Back Yard | 2021-03-14 22:37:35 | 巴幣 2 | 人氣 100

題目連結:


題目大意:
輸入第一列給定兩正整數 n 、 m (1 ≦ n ≦ 10 ^ 6 , 1 ≦ m ≦ 10 ^ 4),代表有 n - 1 個分裝站(編號為 1 ~ n - 1 之節點)、 n 個貨櫃(編號為 n ~ 2n - 1 之節點)以及 m 個貨物。

接著的一列給定 n 個整數,代表 n 個貨櫃在裝貨前就有的貨物重量。再接著一列給定 m 個整數,代表每個貨物的重量。

最後有 n - 1 列輸入,每列給定三整數 a 、 b 、 c,代表分裝站 a 左邊的節點為 b 、 右邊的節點為 c。

已知每個分裝站都有左右兩邊的節點(貨櫃則沒有),因此這 2n - 1 個分裝站以及貨櫃形成了一個系統,該系統裝貨物之方式為:
固定從分裝站 1 (即節點 1)開始;
當貨物在分裝站時,先判斷左側所有節點的貨物總重量有沒有 ≦ 右側總貨物重量,如果有則將貨物移至左側;反之,則移至右側;
當貨物抵達貨櫃時,即停止分裝,直接裝進貨櫃裡。

試問,對於每個預備裝進貨櫃裡的 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

範例輸入 #2
4 5
0 0 0 0
5 3 4 2 1
1 2 3
2 4 5
3 6 7


範例輸出:
範例輸出 #1
8 12

範例輸出 #2
4 6 7 5 5


解題思維:
模擬即可。

可以看到題目的分裝系統是一棵二元樹,所以先根據輸入把樹建立起來之後,從節點 1 往下掃描一次。對於每個節點求出左子樹、右子樹各自的貨物總重。

然後就對於每個貨物依照題目的要求,從節點 1 開始比較左子樹、右子樹的貨物總重量,然後一直往輕的地方走(一樣重則走左邊)。走到遇到貨櫃為止(貨櫃不會有左子樹以及右子樹),此時便可以輸出該貨櫃之編號。

所有貨物都依序按照上述做法即可得到所求。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作