TA的每日心情 | 慵懶 2015-4-10 14:18 |
---|
簽到天數: 78 天 [LV.6]常住居民II
管理員
- 積分
- 3959
|
趕快加入我們來參與討論吧!
您需要 登錄 才可以下載或查看,沒有帳號?加入我們
x
原題:http://www.ioinformatics.org/locations/ioi13/contest/
AC:http://tioj.ck.tp.edu.tw/submissions/12549
可以發現答案具有二分性質,如果我們要判定是否能在P秒內完成,可以將機器人數量乘以P倍,轉變成詢問這一堆機器人有沒有方法一一對應到要搬的物品。這裡提供一個直觀而簡單的策略。
我們鎖定其中一項(比如說重量-弱雞型機器人),將弱雞型機器人以及要搬的物品依照重量一起排序,由大排到小。將這一團東西一拿出,有兩種可能:
1.這是一個弱雞型機器人:因為我們已經排序了,所以這一個機器人可以搬所有尚未拿出的物品!所以我們用一個變數來記錄有多少備用的弱雞型機器人,等到未來要用的時候直接扣除就好。
2.這是一個物品:我們有被我們擱置的小不點機器人,以及備用的弱雞型機器人來匹配,顯然的備用機器人可以任意配對,十分珍貴,所以我們要先找是否有小不點機器人可以把這東西搬走,沒有小不點機器人才使用萬能的備用機器人。當發生沒有機器人可用時即代表配對失敗。配合一些STL可以簡單快速地完成這一題目。
[sojcodepad]4e3e8f00[/sojcodepad]
|
|