AtCoder Grand Contest 003:C - BBuBBBlesort!
問題
解法
連続する3つの要素を逆順にする操作は真ん中の要素を挟んでいる2つの要素を swap することと同じなので,A の奇数番目の要素と偶数番目の要素それぞれがソートされる.なので,ソートされた後の A で奇数番目の要素でないといけないのに偶数番目の要素であるものの数を数え,それを答えにすればよい.O(NlogN).
解答
連続する3つの要素を逆順にする操作は真ん中の要素を挟んでいる2つの要素を swap することと同じなので,A の奇数番目の要素と偶数番目の要素それぞれがソートされる.なので,ソートされた後の A で奇数番目の要素でないといけないのに偶数番目の要素であるものの数を数え,それを答えにすればよい.O(NlogN).