『AGC 003C』BBuBBBlesort!

Problem

传送门：

传送door♂

Solution

这道题其实挺简单的

注意我们可以不花费任何代价交换隔一个的两个字符

那么可以注意到我们的代价只跟奇偶性有关了

可以发现，如果有$k$个奇数在偶数位上，那么必有$k$个偶数在奇数位上

那么我们花的总代价就是$k$（把奇数为放到奇数位上的代价）

离散化之后直接扫一遍统计答案即可

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
inline void _read(int &x)
{
	x = 0;
	char t = getchar();
	while (!isdigit(t)) t = getchar();
	while (isdigit(t))
	{
		x = x * 10 + t - '0';
		t = getchar();
	}
}
 
const int MAXN = 1e5 + 10;
int n, ans;
pair <int, int> in[MAXN];
 
int main()
{
	_read(n);
	for (register int i = 0; i < n; i++)
	{
		_read(in[i].first);
		in[i].second = i;
	}
	sort(in, in + n);
	for (register int i = 0; i < n; i += 2)
	{
		if(in[i].second & 1 != i & 1)
			ans++;
	}
	printf("%d", ans);
	return 0;
}