思路：思维

考虑第二种操作，其实际上就是交换相隔一个位置的两个数，而无法与邻位交换。

因此，我们可以先给奇数位都加一，表示需要与邻位交换也就是使用操作一。

然后排序，再给奇数位对应的数字减一，因为他们的位置没有发生奇偶变换。

之后还有加一的位置，就是必须使用操作一的位置。

代码

C++

#include <bits/stdc++.h>
using namespace std;

int n;
int a[100010];
unordered_map<int, int> mp;

void add(int v){
    for(int i = 1 ; i <= n ; i += 2){
    	mp[a[i]] += v;
	}
}

int main(){
    cin >> n;
    for(int i = 1 ; i <= n ; i ++){
    	cin >> a[i];
	}
    add(1);
    sort(a+1, a+1+n);
    add(-1);
    
    int ans = 0;
    for (auto it = mp.begin(); it != mp.end(); ++it) {
	    if (it->second >= 0) {
	        ans += it->second;
	    }
	}
    cout << ans << endl;
    
    return 0;
}

题目内容

给出一个$n$个互不相同的非负整数，最初是无序的，现在有两种操作：

选择两个连续的数字，然后反转他们的位置，比如[$1,2$]会变成[$2,1$]

选择三个连续的数字，然后反转他们的位置，比如[$1,2,3$]会变成[$3,2,1$]

可以证明，在有限次以上两种操作下，一定可以将数列变为有序。但是如果一直进行第一种操作，那不就变成冒泡排序了吗，所以你要是最小化第一种操作的次数。

现在问在要把所有的数字变成升序的前提下，最少要进行多少次第一种操作？

输入描述

第一行输入一个正整数$n$，代表数字的个数

接下来$n$行，每行一个整数$a_i$,保证这些数字互不相同

$1≤n≤10^5$

$0≤a_i≤10^9$

输出描述

输出一个整数，代表最少进行的操作$1$的次数

样例1

输入

4
2
4
3
1

输出

1

说明

先对最后三个数字进行一次操作$2$，然后再对前两个数字进行一次操作$1$