AOJ1345 Bit String Reordering
Bit String Reordering | Aizu Online Judge
問題概要
長さ のビット列
を、となりあう2つのビットをswapすることを繰り返してランレングス符号が
であるようなビット列に変換するときの最小のswap回数を求めよ。
ランレングス符号は0または1が連続する最大の長さを表した数列のことである。たとえば、ランレングス符号が"1 3 2"となるビット列は"011100"と"100011"の2通り存在する。
制約
ビット列 からswap操作のみを繰り返してランレングス符号が
となるようなビット列に変換できることが保証される。
解法
ありうる2通りのビット列に対して、最小のswap回数を求め、小さい方を出力すれば良い。
最小のswap回数は、左から順に見ていって、ことなるビットの場合は、それより右で一番近いものとswapするを繰り返せば良い。
AIZU ONLINE JUDGE: Code Review
