はまやんはまやんはまやん

hamayanhamayan's blog

BBuBBBlesort! [AGC 003 : C]

問題

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;
}