题目描述
Snuke got an integer sequence of length N from his mother, as a birthday present. The i-th (1≦i≦N) element of the sequence is ai. The elements are pairwise distinct. He is sorting this sequence in increasing order. With supernatural power, he can perform the following two operations on the sequence in any order:
Operation 1: choose 2 consecutive elements, then reverse the order of those elements.
Operation 2: choose 3 consecutive elements, then reverse the order of those elements.
Snuke likes Operation 2, but not Operation 1. Find the minimum number of Operation 1 that he has to perform in order to sort the sequence in increasing order.
Constraints
1≦N≦105
0≦Ai≦109
If i≠j, then Ai≠Aj.
All input values are integers.
输入
The input is given from Standard Input in the following format:
N
A1
:
AN
输出
Print the minimum number of times Operation 1 that Snuke has to perform.
样例输入
4
2
4
3
1
样例输出
1
提示
The given sequence can be sorted as follows:
First, reverse the order of the last three elements. The sequence is now: 2,1,3,4.
Then, reverse the order of the first two elements. The sequence is now: 1,2,3,4.
In this sequence of operations, Operation 1 is performed once. It is not possible to sort the sequence with less number of Operation 1, thus the answer is 1.
题意：给出一个长度为n的序列，有两种操作，1，交换两个相邻的数，2，交换某个数的左右两边相邻的数，求要使该序列变为递增序列，最少需要做多少操作1。
首先我们要求递增序列的数，就先排个序，记录序列中每个数的原始位置，可以发现，第一种操作使两个数的位置改变了奇偶，而第二种操作并没有使数的位置改变奇偶，因此，我们拿排序号的那个数的位置和原始位置进行比较，因为拍好序的位置必定是最终位置，无论之前在哪儿，都一定要到达这个最终位置。计算原始位置和应该在的正确位置的距离，如果是距离是奇数，说明原位置和正确位置的奇偶改变了，那么必定用到了操作1，否则用操作2就可以使数达到正确位置。对于每个数我们记录改动的方式，因为操作1是交换的，那么是对于两个数的操作，若对每个数都记录操作1的次数，就重复记录了一遍，因此对于最终的计数做除2处理去重。即正确结果
#include<bits/stdc++.h>
using namespace std;
struct node
{
int i,val;
} a[100005];
bool cmp(node a,node b)
{
return a.val<b.val;
}
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
for(int i=1; i<=n; i++)
{
scanf("%d",&a[i].val);
a[i].i=i;
}
int sum=0;
sort(a+1,a+1+n,cmp);
for(int i=1; i<=n; i++)
if(abs(a[i].i-i)%2==1) sum++;
printf("%d
",sum/2);
}
}