题意 给你一个数组求其中逆序对(i<j&&a[i]>a[j])的个数
我们来看一个归并排序的过程:
给定的数组为[2, 4, 5, 3, 1]，二分后的数组分别为[2, 4, 5], [1, 3]，假设我们已经完成了子过程，现在进行到该数组的“并”操作：
| a: [2, 4, 5] | b: [1, 3] | result:[1] | 选取b数组的1 | |||
| a: [2, 4, 5] | b: [3] | result:[1, 2] | 选取a数组的2 | |||
| a: [4, 5] | b: [3] | result:[1, 2, 3] | 选取b数组的3 | |||
| a: [4, 5] | b: [] | result:[1, 2, 3, 4] | 选取a数组的4 | |||
| a: [5] | b: [] | result:[1, 2, 3, 4, 5] | 选取a数组的5 |
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 500005;
int a[N], t[N], n;
long long cnt;
void merge(int l, int m, int r)
{
int pl = l, pr = m + 1, p = 0;
while(pl <= m && pr <= r)
{
if(a[pl] <= a[pr]) t[p++] = a[pl++];
else
{
t[p++] = a[pr++];
cnt += m + 1 - pl;
}
}
while(pl<=m) t[p++] = a[pl++];
while(pr<=r) t[p++] = a[pr++];
memcpy(a + l, t, sizeof(int)*p);
}
void mergeSort(int l, int r)
{
if(l >= r) return;
int m = (l + r) >> 1;
mergeSort(l, m);
mergeSort(m + 1, r);
merge(l, m, r);
}
int main()
{
while(scanf("%d", &n), n)
{
for(int i = 0; i < n; ++i)
scanf("%d", &a[i]);
cnt = 0;
mergeSort(0, n - 1);
printf("%lld\n", cnt);
}
return 0;
}
Description
In this problem, you have to analyze a particular sorting algorithm. The algorithm processes a sequence of n distinct integers by swapping two adjacent sequence elements until the sequence is
sorted in ascending order. For the input sequence Input
Output
Sample Input
5 9 1 0 5 4 3 1 2 3 0
Sample Output
6 0
POJ 2299 Ultra-QuickSort(归并排序·逆序对)
原文：http://blog.csdn.net/acvay/article/details/44984309