ETH官方钱包

切換
舊版
前往
大廳
主題

ZeroJudge - e538: 11389 - The Bus Driver Problem 解題心得

Not In My Back Yard | 2019-11-20 12:46:31 | 巴幣 0 | 人氣 162

題目連結:


題目大意:
題目有多筆測試資料。每筆佔三列輸入。第一筆給定三正整數 n 、 d 、 r (1 ≦ n ≦ 100 , 1 ≦ d ≦ 10000 , 1 ≦ r ≦ 5),代表有 n 位公車司機、早晚班的路線各 n 條、早晚班負責的路線總長超過 d 單位後,每單位多支付 r 元作為加班費。

第二列、第三列各有 n 個正整數(皆不超過 10000),分別代表早班以及晚班的路線之長度。

而每位公車司機都要分配到一條早班和晚班的路線。求在最佳的分配下,最少需要支付多少加班費。



範例輸入:
2 20 5
10 15
10 15
2 20 5
10 10
10 10
0 0 0


範例輸出:
50
0


解題思維:
因為每位司機都會被分配到路線,所以沒有路線沒有被使用到。因此可以直接將早班的距離由小到大排且晚班的路線由大到小排,然後一一分配給司機們(反過來排也行,總之早班、晚班的排序方式要相反)。

而這樣子便會是最佳的分配之一。因為如果進行其他分配容易「浪費」尚未跑滿 d 單位的那些司機。

接著跑過一次分配後每位需要付多少加班費即可知道所求。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。
追蹤 創作集

作者相關創作

更多創作