查看: 871|回復: 0

[HOJ] 361 - [JOI] IOI草

[複製鏈接]
  • TA的每日心情
    開心
    2015-4-12 10:09
  • 簽到天數: 137 天

    [LV.7]常住居民III

    142

    主題

    686

    帖子

    3559

    積分

    邁向天堂

    蘇多門

    Rank: 8Rank: 8

    積分
    3559

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

    發表於 2015-3-26 20:30:03 | 顯示全部樓層 |閱讀模式

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

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

    x
    本帖最後由 domen111 於 2015-3-26 20:51 編輯

    Problem: http://hoj.twbbs.org/judge/problem/view/361
    AC: http://hoj.twbbs.org/judge/judge/submission/33650

    本來一直想著用逆序數對做,想說要枚舉最高的草的位置,不過我們解法的想法和逆序數對沒什麼關係

    解法:
    從最低的草開始,如果離左邊比較近就移到左邊,否則就移到右邊;若遇到相同高度的就從移動次數較少的(離左邊或右邊較近的)優先算
    實作上我是使用BIT,BIT初始值為1,如果已經移走了就把BIT[ i ]設為0

    剛剛看到用逆序數對的觀念其實也能解: http://garbagecode.blogspot.tw/2 ... lem-361-1b-ioi.html
    問了一下,做法是對每個數算左右兩邊的逆序數,其實本質上是一樣的做法,不過好像更簡單

    Code:
    [sojcodepad]141ef822[/sojcodepad]
    蘇多門 domen111
    My Web: https://sites.google.com/site/domenprg/
    回復

    使用道具 檢舉

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

    本版積分規則

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