Posted on 2012-01-16 15:54
C小加 閱讀(358)
評論(0) 編輯 收藏 引用 所屬分類:
解題報告
用歸并排序求逆序數。歸并排序中適當的位置加上cnt+=n1-i，就可以了。
#include<cstdio>
#include<iostream>
using namespace std;
const int MAXM=1000003;
const int INF=0x7fffffff-1;
long long cnt;
int arr[MAXM];
int temp1[MAXM/2+1], temp2[MAXM/2+1];
// 歸并排序中的合并算法
void Merge(int array[], int start, int mid, int end)
{
int n1, n2;
n1 = mid - start + 1;
n2 = end - mid;
// 拷貝前半部分數組
for (int i = 0; i < n1; i++)
{
temp1[i] = array[start + i];
}
// 拷貝后半部分數組
for (int i = 0; i < n2; i++)
{
temp2[i] = array[mid + i + 1];
}
// 把后面的元素設置的很大
temp1[n1] = temp2[n2] = INF;
// 逐個掃描兩部分數組然后放到相應的位置去
for (int k = start, i = 0, j = 0; k <= end; k++)
{
if (temp1[i] <= temp2[j])
{
array[k] = temp1[i];
i++;
}
else
{
cnt+=n1-i;//逆序對的個數
array[k] = temp2[j];
j++;
}
}
}
// 歸并排序
void MergeSort(int array[], int start, int end)
{
if (start < end)
{
int i;
i = (end + start) / 2;
// 對前半部分進行排序
MergeSort(array, start, i);
// 對后半部分進行排序
MergeSort(array, i + 1, end);
// 合并前后兩部分
Merge(array, start, i, end);
}
}
int main()
{
//freopen("in.txt","r",stdin);
int t;
scanf("%d",&t);
while(t--)
{
cnt=0;
int n;
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d",arr+i);
}
MergeSort(arr,0,n-1);
printf("%lld\n",cnt);
}
return 0;
}