sdutacm-数据结构实验之排序五:归并求逆序数
数据结构实验之排序五:归并求逆序数
TimeLimit: 50MS Memory Limit: 65536KB
SubmitStatistic
对于数列a1,a2,a3…中的任意两个数ai,aj(i < j),如果ai> aj,那么我们就说这两个数构成了一个逆序对;在一个数列中逆序对的总数称之为逆序数,如数列16 3 7 2 49中,(6,4)是一个逆序对,同样还有(3,2),(7,4),(6,2),(6,3)等等,你的任务是对给定的数列求出数列的逆序数。
Input
输入数据N(N<= 100000)表示数列中元素的个数,随后输入N个正整数,数字间以空格间隔。
Output
输出逆序数。
ExampleInput
10
109 8 7 6 5 4 3 2 1
ExampleOutput
45
Hint
Author
xam
#include <iostream> #include<bits/stdc++.h> using namespace std; long long ans;//注意这里的数据类型为坑点 int a[100010],temp[100010]; void merge(int s1,int e1,int s2,int e2) { int p1,p2,p; p = 0; p1 = s1;//左序列开头 p2 = s2;//右序列开头 while(p1<=e1&&p2<=e2) { if(a[p1]<=a[p2]) temp[p++] = a[p1++]; else { temp[p++] = a[p2++]; ans += e1-p1+1; //归并时取第二序列每个元素时第一序列中剩余元素个数即为本次该元素的逆序数 } } while(p1<=e1)//处理最后的元素 temp[p++] = a[p1++]; while(p2<=e2) temp[p++] = a[p2++]; int i; for(i=s1;i<=e2;i++)//把缓存数列再赋回去 a[i] = temp[i-s1]; } void merge_sort(int s,int e) { int m; if(s<e) { m = (s+e)/2; merge_sort(s,m);//分割函数 merge_sort(m+1,e); merge(s,m,m+1,e);//归并函数 } } int main() { int n,i; ans = 0; scanf("%d",&n); for(int i= 0;i<n;i++) { scanf("%d",&a[i]); } merge_sort(0,n-1); printf("%lld\n",ans); return 0; } /*************************************************** User name: jk160505徐红博 Result: Accepted Take time: 48ms Take Memory: 932KB Submit time: 2017-02-23 16:58:03 ****************************************************/