蓝桥杯练习系统（算法训练）ALGO-950 逆序数奇偶

资源限制

内存限制：256.0MB   C/C++时间限制：1.0s   Java时间限制：3.0s   Python时间限制：5.0s

问题描述

　　老虎moreD是一个勤于思考的青年，线性代数行列式时，其定义中提到了逆序数这一概念。不过众所周知我们只需要知道逆序数的奇偶性就行了，为了防止计算上的失误，moreD准备编写一个小程序来判定。只要判断奇偶性就行了哦！
　　另外作为一个技术宅，moreD对线性代数中最小下标为1非常不满，于是所有下标均从0开始。

输入格式

　　一个测试点包含多组数据，你需要不断读入直到输入结束。
　　每组数据第一行为一个n，接下来第二行输入n个数字，是一个0到n-1的排列。

输出格式

　　输出若干行，每行表示对应组数据逆序数奇偶性，奇数输出odd，偶数输出even。

样例输入

5
0 1 2 3 4
5
4 3 1 2 0

样例输出

even
odd

数据规模和约定

　　设每组测试点T个数据
　　1<=T<=10
　　1<=n<=100000

首先看暴力方法，超时（仅供理解题意）：

4 3 1 2 0，求逆序数的方法：

• 对于第1个数字4，前面没有比它大的数，逆序数为0
• 对于3，前面有比它大的数字4，逆序数为1
• 对于1，前面有4,3，都比它大，逆序数为2
• 对于2 ，前面有4,3,1，两个比它大，逆序数为2
• 对于0，前面有4,3,1,2，都比它大，逆序数为4

因此，该序列的逆序数=0+1+2+2+4=9，为odd

#include<iostream>
using namespace std;int main(){int n;while(cin>>n){int a[n];for(int i=0;i<n;i++){cin>>a[i];}long long int sum=0;for(int i=1;i<n;i++){for(int j=0;j<i;j++){if(a[j]>a[i]) sum++;}}if(sum%2==0) cout<<"even"<<endl;else cout<<"odd"<<endl;}return 0;
}

归并算法

#include<iostream>
using namespace std;
const int N=100005;
int a[N];//待排序的数组
int tmp[N];
int res=0;void msort(int l,int r){if(l==r) return;//只有一个数 int mid=(l+r)>>1;msort(l,mid);msort(mid+1,r);//合并 int i=l,j=mid+1,k=l;while(i<=mid&&j<=r){if(a[i]<=a[j]) tmp[k++]=a[i++];else{tmp[k++]=a[j++];res+=mid-i+1;}} while(i<=mid) tmp[k++]=a[i++];while(j<=r) tmp[k++]=a[j++];for(int i=l;i<=r;i++) a[i]=tmp[i];
}
int main(){int n;while(cin>>n){res=0;for(int i=0;i<n;i++){cin>>a[i]; }msort(0,n-1);if(res%2==0) cout<<"even"<<endl;else cout<<"odd"<<endl;}return 0;
} 

思路：归并算法。在右段取数时，计算逆序数，即取右段中的数时，该数的逆序数为左段中比它大的数。