查看: 838|回復: 0

[HOJ] [TIOJ1403][CEOI 2003]16 - 賽車 (The Race)

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

    [LV.6]常住居民II

    176

    主題

    612

    帖子

    3959

    積分

    管理員

    Rank: 9Rank: 9Rank: 9

    積分
    3959

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

    發表於 2015-3-13 16:14:40 | 顯示全部樓層 |閱讀模式

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

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

    x
    原題:http://www.ceoi2003.de/www/downloads/therace-en.pdf
    TIOJ:http://tioj.ck.tp.edu.tw/problems/1403
    HOJ:http://hoj.twbbs.org/judge/problem/view/16


    AC:http://tioj.ck.tp.edu.tw/submissions/11845

    本問題分為兩問題,第一問題可用BIT完成,不過[tex]V%5Cleq100[/tex],暴力加一加也行,重點在第二部分,當然我們不能枚舉所有pair,這樣肯定超時。此時我們可以採用模似法,反正超車一定是前一輛車超過下一輛車,我們可以先線性掃瞄有哪一些車子要超過後面的車子,放入一個priority queue中依照相遇時間以及位置作為基準一一拿出,每次拿出後,更新這兩台車子的位置,以及新出來的超車關係,就能完成這題了。

    [sojcodepad]281e9ac1[/sojcodepad]
    回復

    使用道具 檢舉

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

    本版積分規則

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