ACM

南陽oj題目地址：http://acm.nyist.edu.cn/JudgeOnline/problem.php?pid=117

時間限制：2000ms | 內存限制：65535KB 難度：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

 

  求逆序數：用歸並排序來做，效率還是很高的； 歸並排序利用分治的思想，先把一個數組分成一個個序列，然後對一個個序列排序，把排好序的序列，在合並到原來的數組中。

 

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=1000001;
int a[maxn],b[maxn];
long long sum;
/**
  歸並
*/
void Merge(int begin,int mid,int end){
    int i=begin,j=mid+1,pos=begin;
    //對一個個序列排序的過程
    while(i<=mid && j<=end){
        if(a[i]<=a[j]){
            b[pos++]=a[i++];
        }else{
            b[pos++]=a[j++];
            sum+=mid-i+1;//求逆序數
        }
    }
    while(i<=mid) b[pos++]=a[i++];
    while(j<=end) b[pos++]=a[j++];
    for(int i=begin,j=begin;i<=end;i++,j++)
        a[i]=b[j];
}
/**
  排序
*/
void Sort(int begin,int end){
    if(begin<end){ int="" mid="(begin+end)/2;" sum="0;" i="1;i<=n;i++)" return="" pre="">



</end){></algorithm></cstring></cstdio>