题目描述

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≦10 5
0≦Ai≦10 9
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.

题目不难理解，当然也没有理解透┭┮﹏┭┮
刚开始我觉得这个挺像归并排序的
但是这样又肯定超时
然后我也没有认真想好就交，下次不能这样 
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
struct data
{
    int x=0,p=0;
};
bool cmp(data a,data b)
{
   return   a.x<b.x;
}
int main()
{   data a[100005];
    data b[100005];
    int l=1,n,i;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&a[i].x);
        a[i].p=i;
    }
    sort(a+1,a+n+1,cmp);
    int ans=0;
    for(i=1;i<=n;i++)
    {
        if(abs(a[i].p-i)%2!=0)
        {
            ans++;
        }
    }
    printf("%d\n",ans/2);
    return 0;
}
View Code

这代码是不是超级简单

当模拟真的很复杂但是想不出其他方法了，应该就是找规律

我们的最终目标是让从小到大排好

只要元素与它应该在的位置的距离是偶数，就一定不需要消耗方法1.