主題

ZeroJudge - f632: 渡船頭 解題心得

Not In My Back Yard | 2021-01-29 00:00:06 | 巴幣 0 | 人氣 45

題目連結:


題目大意:
輸入第一列給定四正整數 T1 、 T2 、 K 、 P (1 ≦ T1 < T2 ≦ 10000 , K ≠ 0 , 1 ≦ P ≦ 100),代表船老闆營業時間為 T1(含)~ T2(含),從 T1 開第一班後每班船隔 K 單位時間才開下一班,每班最多載 P 位乘客。

接著有若干列(≦ 100000 列)輸入,每列給定兩整數 t 、 m ,代表該名乘客的抵達時間以及給的小費金額。對於每班船而言,給越多小費的乘客越先上船。

試問,總共載了多少位客人又賺取了多少的小費?



範例輸入:
2 5 2 2
1 10
2 3
2 8
2 5
4 30
3 5
3 20
7 40
3 10
5 15


範例輸出:
4 68


解題思維:
先把所有乘客的抵達時間以及小費金額存起來,然後將所有乘客按照抵達時間由小到大排序。

接著宣告一個優先佇列 G(Priority Queue) 用以存取小費金額最大的乘客並令一變數 T = T1。

然後將所有抵達時間 ≦ T 的乘客之小費金額都丟進 G 裡(因為剛剛有排序,所以很方便),接著從 G 之中抓取 P 位乘客(如果不夠 P 位,就全數抓出即可),而這幾位即是小費給最多的前幾位乘客,因此讓他們搭上時間 T 開的這班船。

然後將 T 加上 K 然後重複上面的步驟直到 T > T2。過程中每一班所載乘客數、小費金額全部加總即是所求。




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

創作回應

更多創作