求逆序数之分治排序
求逆序数时间限制：2000 ms | 内存限制：65535 KB
难度：5
描述
在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。
现在，给你一个N个元素的序列，请你判断出它的逆序数是多少。
比如 1 3 2 的逆序数就是1。
输入
第一行输入一个整数T表示测试数据的组数（1<=T<=5)
每组测试数据的每一行是一个整数N表示数列中共有N个元素（2〈=N〈=1000000）
随后的一行共有N个整数Ai(0<=Ai<1000000000)，表示数列中的所有元素。
数据保证在多组测试数据中，多于10万个数的测试数据最多只有一组。
输出
输出该数列的逆序数
样例输入
2
2
1 1
3
1 3 2样例输出
0
1
思路：先分治后归并
AC代码：#include<iostream>
#include<string.h>
#include<string>
#define N 1000001
using namespace std;
longa,b;
long long num;//尼玛的这里让我错了好几次。。。
void merge(int p,int q,int r,int s)
{ int a1=p,k=p,c=r;
while(a1<=q&&c<=s)
{if(a<=a) b=a;
else{b=a;num+=q-a1+1;}
}
if(a1>q)
for(;c<=s;++c)
b=a;
if(c>s)
for(;a1<=q;++a1)
b=a;
for(;p<k;++p)
a=b;
}
void merge_sort(int p,int r)
{ if(p<r)
{int q=(p+r)/2;
merge_sort(p,q);
merge_sort(q+1,r);
merge(p,q,q+1,r);
}
}
intmain()
{int Case;
cin>>Case;
while(Case--)
{ memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
num=0;
int n;
cin>>n;
for(int i=0;i<n;++i)
cin>>a;
merge_sort(0,n-1);
cout<<num<<endl;
}return 0;
}
作者：smallacmer 发表于2012-2-17 8:42:53 原文链接
页:
[1]