Download presentation
Presentation is loading. Please wait.
1
10440: Ferry Loading II ★★☆☆☆ 題組：Problem Set Archive with Online Judge
解題者：許雯涵 解題日期：2019年4月25日 題意：有一艘渡輪要載m輛車到河的另一岸，單程需要t分鐘，每趟最多可以載n輛車，求載完所有車到對岸所需的最少時間和趟數？
2
🚗🚗 🚗🚗 🚗🚗 🚗🚗 🚗🚗 🚗🚗 🚗🚗 🚗🚗 🚗🚗 🚗🚗 題意範例： 1 //1筆測資
1 //1筆測資 //每趟最多載2輛車，單程5分鐘，總共有5輛車要載 //每輛車到達可以被載的地方的時間 →31 3 //最短31分鐘，最少3趟 時間：12 時間：14 時間：0 時間：6 時間：10 時間：7 時間：16 時間：21 時間：11 時間：31 時間：26 出發岸 抵達岸 🚗🚗 🚗🚗 🚗🚗 🚗🚗 🚗🚗 🚗🚗 🚗🚗 🚗🚗 🚗🚗 🚗🚗
3
（在出發岸和抵達岸的車以其到達出發岸的時間代表）
船的狀態 出發岸 抵達岸 6 7 運送中 10 7、10 11 12 返程中 7、10、12 14 7、10、12、14 16 21 12、14 6、7、10 26 31 6、7、10、12、14
4
解法：greedy method，每趟載滿n輛車（最少趟數），載不滿n輛車的第一趟載（最少時間，由於每輛車到的時間為遞增排序，每趟必定要等第n輛車到的時間）。
解法範例：無 討論：無
Similar presentations
