Submission #845984

---

Source Code Expand

//操作2は「2つ飛ばしの要素を交換」と読み直せる -> indexの偶奇が大事！。
//奇数indexにあってソート後に偶数indexになるもの, 偶数indexにあってソート後に奇数indexになるものの個数を数える。
//それを２で割ったものが下界。

#include <iostream>
#include <algorithm>
using namespace std;

int n;
int a[100000];
int b[100000];

int main() {
	int i;
	
	cin >> n;
	for (i = 0; i < n; i++) cin >> a[i];
	for (i = 0; i < n; i++) b[i] = a[i]; sort(b, b + n);
	
	int ans = 0;
	for (i = 0; i < n; i++) {
		int index = lower_bound(b, b + n, a[i]) - b;
		if (index % 2 != i % 2) {
			ans++;
		}
	}
	ans /= 2;
	cout << ans << endl;
	return 0;
}

Submission Info

Judge Result