問題
http://agc003.contest.atcoder.jp/tasks/agc003_c
N要素の数列がある。
これを2種の方法で要素を入れ替えて昇順ソートする
- 操作1 : 隣り合う2つの要素を選んで入れ替える
- 操作2 : 1つ飛ばしの2つの要素を選んで入れ替える
操作2の回数は何回でもいい。
操作1の最小回数を求めよ。
1 <= n <= 10^5
0 <= Ai <= 10^9
考察
1. 「操作2」は1つ飛ばしの2つの要素を入れ替えることは無限にできる
2. つまり、偶数番目の数列と奇数番目の数列は自由にソーティングできるということ
3. そのため、昇順ソートするためには、昇順ソート後の番目と現在の番目の偶奇のみ一致してればいいことになる
4. 操作1でこの偶奇を合わせてやればよい
5. まず、与えられた数列の奇数番目の数をカウントする -> cnt
6. 次に与えられた数列を昇順ソートし、その数列の奇数番目の数をカウントする -> cnt2
7. この2つのカウントした数の差が操作1で合わすべき数の個数となるので、これを答えれば答え
実装
http://agc003.contest.atcoder.jp/submissions/849171
int N; int A[101010]; //----------------------------------------------------------------- int main() { cin >> N; rep(i, 0, N) scanf("%d", &A[i]); map<int, int> cnt; rep(i, 0, N) if (i % 2 == 0) cnt[A[i]]++; sort(A, A + N); map<int, int> cnt2; rep(i, 0, N) if (i % 2 == 0) cnt2[A[i]]++; int ans = 0; for (auto p : cnt) { ans += abs(cnt2[p.first] - p.second); } cout << ans << endl; }