h029. 202001_4 貨物分配
標籤 : APCS
通過比率 : 237人/284人 ( 83% ) [非即時]
評分方式:
Tolerant

最近更新 : 2024-01-24 16:58

內容

某工程公司設計了一個自動分裝的系統。貨物會一個一個的被送進此系統,經過一些切換器的轉送後,會被輸送到 $n$ 個貨箱。

系統有 $(n–1)$ 個切換器與 $n$ 個貨箱。每個切換器有一個入口以及左右兩個出口,切換器的出口會接到其他切換器或是連接到貨箱,貨箱則只有入口。

下圖是一個 $n=7$ 的例子,圓代表切換器,方形代表貨箱,請注意編號 $1 \sim (n–1)$ 的裝置是切換器,貨箱編號是 $n \sim (2n–1)$,且貨物入口一定是 $1$ 號切換器的入口。

每一個切換器會分別記錄左右兩個出口所通往貨箱的總重量,當貨物進入此切換器時,切換器會將貨物轉送到「貨箱總重量比較輕的那個出口」,如果兩邊一樣重,則送往左邊。

以上圖的例子來說,假設每一個貨箱目前的重量如各矩形下方的標示,下一個到達的貨物的運送過程如下:
$1$ 號切換器左邊出口是連到 $\{13, 10, 7\}$ 三個貨箱,目前總重 $5+6+9=20$;右邊出口連到的是 $\{12, 8, 11, 9\}$ 四個貨箱,目前總重 $7+2+8+1=18$,因此貨物會由右邊出口送到 $5$ 號切換器。 $5$ 號切換器的左邊與右邊的貨箱總重是一樣的($7+2=8+1$),因此貨物由左出口送至 $6$ 號切換器。最後,$6$ 號切換器將貨物送到 $8$ 號貨箱 ($7>2$)。貨物進入貨箱後就存放在該貨箱,該貨物的重量就會加入該貨箱的總重,因此可能影響下一個貨物的運送路徑。

輸入此系統的連接架構與貨箱目前的重量,以及接下來依序進入的 $m$ 個貨物的重量,請計算這 $m$ 個貨物分別會被送到哪一個貨箱。

輸入說明

第一行為兩個正整數 $n$ 和 $m$,其中 $n \leq 10^5$ 且 $m \leq 100$。

第二行有 $n$ 個非負整數,依序是編號為 $n \sim (2n–1)$ 各個貨箱初始的重量。

第三行是 $m$ 個正整數,代表接下來依序進入的貨物重量。全部貨箱初始的重量與貨物重量總和不會超過 $10^9$。

第四行開始有 $(n–1)$行,這些是系統架構的資訊:每一行有三個整數 $p$、$s$ 與 $t$ ,代表裝置 $p$ 的左右出口分別接到裝置 $s$ 與 $t$ ,其中 $p$ 一定是一個切換器的編號 $(1 ≤ p < n)$ 。同一行數字之間以空白間隔。

 

本題包含三個子題組,每個子題組配分如下:

  • 第 1 子題組 20 分:$n \leq 10$,$s=2p$,$t=2p+1$,所有貨箱初始重量為 $0$。
  • 第 2 子題組 30 分:$n \leq 1000$,$s=2p$,$t=2p+1$。
  • 第 3 子題組 50 分:無其他限制。
輸出說明

輸出一行有 $m$ 個整數,依序代表接下來進入系統的 $m$ 個貨物所進入到的貨箱編號,數字之間以一個空白間隔。

範例輸入 #1
4 5
0 0 0 0
5 3 4 2 1
1 2 3
2 4 5
3 6 7
範例輸出 #1
4 6 7 5 5
範例輸入 #2
7 2
9 2 1 6 8 7 5
2 3
1 2 5
2 3 7
3 13 10
4 11 9
6 12 8
5 6 4
範例輸出 #2
8 7
測資資訊:
記憶體限制: 512 MB
提示 :

範例二的架構即是題目中的圖。

標籤:
APCS
出處:
2020年1月APCS [管理者: ktlai@cmgsh. ... (賴楷宗) ]

本題狀況 本題討論 排行

編號 身分 題目 主題 人氣 發表日期
42065 timeflew (TLE) h029
90 2024-09-23 23:03
41421 glps1004@gma ... (Ian) h029
APCS 202001全解析
109 2024-07-25 12:02
40824 glps1004@gma ... (Ian) h029
119 2024-06-14 17:06
40359 qerpzzea@gma ... (賽希爾 cecill(陳宥穎)) h029
167 2024-05-13 20:36
38923 bobobo0413 (Andy) h029 218 2024-01-03 22:58