竹園論壇

標題: [IOI2013][Gready][二分搜]1815 - 機器人(Robots) [打印本頁]

作者: Sylveon 時間: 2015-3-22 19:41
標題: [IOI2013][Gready][二分搜]1815 - 機器人(Robots)
原題：http://www.ioinformatics.org/locations/ioi13/contest/
AC：http://tioj.ck.tp.edu.tw/submissions/12549

可以發現答案具有二分性質，如果我們要判定是否能在P秒內完成，可以將機器人數量乘以P倍，轉變成詢問這一堆機器人有沒有方法一一對應到要搬的物品。這裡提供一個直觀而簡單的策略。

我們鎖定其中一項(比如說重量-弱雞型機器人)，將弱雞型機器人以及要搬的物品依照重量一起排序，由大排到小。將這一團東西一拿出，有兩種可能：

1.這是一個弱雞型機器人：因為我們已經排序了，所以這一個機器人可以搬所有尚未拿出的物品！所以我們用一個變數來記錄有多少備用的弱雞型機器人，等到未來要用的時候直接扣除就好。
2.這是一個物品：我們有被我們擱置的小不點機器人，以及備用的弱雞型機器人來匹配，顯然的備用機器人可以任意配對，十分珍貴，所以我們要先找是否有小不點機器人可以把這東西搬走，沒有小不點機器人才使用萬能的備用機器人。當發生沒有機器人可用時即代表配對失敗。配合一些STL可以簡單快速地完成這一題目。

[sojcodepad]4e3e8f00[/sojcodepad]

歡迎光臨竹園論壇 (http://forum.tfcis.org/)