2019TOI1214 新手同好會 3. 站牌廣告 (BusStop) {試題連結}
問題敘述
為因應全球暖化,政府近年來提倡大眾運輸以減少交通工具所產生的碳排放量,而公車站牌所帶來的人流也可以為廣告看板增加曝光度!各廠商都想在最多人經過的站牌擺放自家的廣告,政府看準了這項商機,為了增加國庫收入以替人民謀福祉,決定依據站牌人流的多寡來制定廣告價格的高低以獲取最大的效益。 假設公車路線只有一條,公車會來回行駛。去程從站牌 1 經過站牌 2,依續到最後一站 B; 回程從站牌 B 經過站牌 (B-1),依續到站牌 1。目前已統計出乘客之上下車站牌,請你幫忙統計經過各站牌之人流數量,找出最多與最少人經過之站牌。
範例 1 圖示如下 (輸入、輸出格式請見下頁範例 1):
最少人流車站為(1) 號站牌 ( 0 人經過 ),最多為(5) 號站牌 ( 3 人經過 )。
評分說明 此題目測資分成三組,每組測資有多筆測試資料,需答對該組所有測試資料才能獲得該 組分數,各組詳細限制如下。
子任務1 分數 50額外輸入限制乘客路線為單一方向 (Y > X),且最多與最少人流之站牌皆僅有一個。
子任務2 分數 30 乘客路線可能為雙向,且最多與最少人流之站牌皆僅有一個。
子任務3 分數 20 無特別限制。
第一行輸入兩個正整數,第一個數 B (2 ≤ B ≤ 1000) 代表公車共經過幾個公車站牌(站牌 編號為 1, 2, 3, …, B);第二個數 P (1 ≤ P ≤ 1000) 則表示共有多少人要搭乘此公車。接下來共 輸入 P 行,每行輸入兩個正整數,以空白隔開,表示該位乘客的上車站牌 X 與下車站牌 Y ( 1 ≤ X,Y ≤ B,X<>Y)。
共輸出兩個正整數,以一個空白區隔,第一個正整數 N (1 ≤ N ≤ B) 代表最少人流之公車 站牌(若有多個則輸出編號最小者),第二個正整數 M (1 ≤ M ≤ B)則代表最多人流之公車站牌 (若有多個則輸出編號最大者)。
8 3 2 7 5 3 5 8
1 5
10 9 1 5 10 5 4 2 8 10 4 5 7 10 2 4 10 8 8 9
1 9
1000 2 1 1000 1 1000
1 1000
ID | User | Problem | Subject | Hit | Post Date |
31794 | laijason0512 ... (賴嘉澤) | e796 | 407 | 2022-08-20 09:40 |