[AGC003C] BBuBBBlesort! 题解

题目链接：[AGC003C] BBuBBBlesort!

题意：

给定一个序列 \(a\)，元素两两不同，可以使用两种操作。

1. 翻转相邻两个元素。
2. 翻转相邻三个元素。

问怎么操作使这个序列变成升序，并使操作一的次数最少。输出这个最少的次数。

输入：\(n\) 和 \(a_i\) 。输出：答案。

数据范围：

\(1\le n \le 10^5,~0 \le a_i \le 10^9\) ​。

先离散化一下（不用去重），这样权值就是正确的编号。

可以发现，只使用操作二可以将奇数位&偶数位的数分别排序

但是在奇数位上的数编号可能不是偶数，

这种情况必须用一下操作一，把奇数位和偶数位上错位的两个憨憨交换一下。

时间复杂度 \(\mathcal{O}(n \log n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define N ((int)(1e5 + 15))

int ans, a[N], b[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n; cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    memcpy(b, a, (n + 1) * sizeof(int)); sort(b + 1, b + 1 + n);
    for(int i = 1; i <= n; i++) a[i] = lower_bound(b + 1, b + 1 + n, a[i]) - b;
    for(int i = 1; i <= n; i++) ans += ((a[i] & 1) != (i & 1));
    cout << ans / 2 << '\n';
    return 0;
}