Download presentation
Presentation is loading. Please wait.
1
11729 - Commando War ★★☆☆☆ 題組：Problem Set Archive with Online Judge
解題者：陳仕軒、張富鈞、盛琮舜 解題日期：2015年3月17日 題意：你有n個士兵，每位士兵都必須花B分鐘交代任務，然後他會不間斷的執行J分鐘完成任務，不能同時給兩位士兵交代任務，但是士兵們可以同時執行他們各自的任務，你要選擇任務交代的順序，使得任務盡早完成。輸入包含多組測資，每組測資第一列為士兵個數N(1<=N<=1000)，接下來每列兩個數字，分別為交代時間B(1<=B<=10000)和執行時間J (1<=J<=10000)，當N=0時代標測試結束。
2
題意範例： 3 2 5 3 2 2 1 Case 1: 8 3 3 3 4 4 5 5 Case 2: 15 解法： (1) B的總合是固定的，那麼要使得答案最小，就要盡量讓J的時間範圍重疊，因此將J由大排到小。 (2)最後一位執行完不代表其他人已經執行完了，所以你要判斷最後一位結束的是哪位，如右圖下方。
3
解法範例： (1)5 + 5 (2) > 5 + 5 (3) > 此題答案： = 15
4
討論：無
Similar presentations
