查看: 827|回復: 0

[TIOJ] [IOI2013][Gready][二分搜]1815 - 機器人(Robots)

[複製鏈接]
  • TA的每日心情
    慵懶
    2015-4-10 14:18
  • 簽到天數: 78 天

    [LV.6]常住居民II

    176

    主題

    612

    帖子

    3959

    積分

    管理員

    Rank: 9Rank: 9Rank: 9

    積分
    3959

    台南一中資訊社新手達陣程式設計達人 - 2014

    發表於 2015-3-22 19:41:43 | 顯示全部樓層 |閱讀模式

    趕快加入我們來參與討論吧!

    您需要 登錄 才可以下載或查看,沒有帳號?加入我們

    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]
    回復

    使用道具 檢舉

    您需要登錄後才可以回帖 登入 | 加入我們

    本版積分規則

    快速回覆 返回頂部 返回列表