加賀一稿一記

心は戦国

AGC003C BBuBBBlesort!

atcoder.jp
600埋め

問題概要
長さNの数列をソートしたい。(1<=N<=10^5,全ての要素は異なる。)
2種類の操作がある。

  1. 隣り合う2つの要素を入れ替える。
  2. 1つ飛ばしの2つの要素を入れ替える。

操作2は何回行っても良い。
操作1は最小何回で達成できるか。

考察
操作2のコストが0なので、偶数番目,奇数番目の要素は自由に配置を変えられる。
「ソート後の位置が奇数番目なのに、元の位置が偶数番目」な要素は、
「ソート後の位置が偶数番目なのに、元の位置が奇数番目」な要素と入れ替える必要がある。
要素の元の位置を保存したうえでソートし、数える。

提出
→AC
やったぜ。