【秋招笔试题】讨厌冒泡排序

题解：免费的操作是分别在奇偶下标进行排序，收费的操作会改变他们下标的奇偶性，那么直接统计在排序后有多少元素的下标发生变化了即可。

#include <iostream>
#include <vector>
#include <algorithm>
#include "map"
using namespace std;
#define int long long
map<int,int> mp;
signed main() {std::ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);int n;cin >> n;vector<int> arr(n);for (int i = 0; i < n; i++) {cin >> arr[i];mp[arr[i]] = (i & 1);}sort(arr.begin(),arr.end());int res = 0;for (int i = 0; i < n; ++i) {res += (i & 1) ^ (mp[arr[i]]);}cout << res / 2;}