竹園論壇

標題: 361 - [JOI] IOI草 [打印本頁]

作者: domen111 時間: 2015-3-26 20:30
標題: 361 - [JOI] IOI草
本帖最後由 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]

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