Description
设a[0…n-1]是一个包含n个数的数组，若在i<j的情况下，有a[i]>a[j]，则称(i, j)为a数组的一个逆序对（inversion）。
比如 <2,3,8,6,1> 有5个逆序对。请采用类似“合并排序算法”的分治思路以O(nlogn)的效率来实现逆序对的统计。
一个n个元素序列的逆序对个数由三部分构成：
（1）它的左半部分逆序对的个数，（2）加上右半部分逆序对的个数，（3）再加上左半部分元素大于右半部分元素的数量。
其中前两部分（1）和（2）由递归来实现。要保证算法最后效率O(nlogn)，第三部分（3）应该如何实现？
此题请勿采用O(n^2)的简单枚举算法来实现。
并思考如下问题：
（1）怎样的数组含有最多的逆序对？最多的又是多少个呢？
（2）插入排序的运行时间和数组中逆序对的个数有关系吗？什么关系？
输入格式
第一行：n，表示接下来要输入n个元素，n不超过10000。
第二行：n个元素序列。
输出格式
逆序对的个数。
输入样例
5
2 3 8 6 1
输出样例
5
#include<cstdio>
#include<vector>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int a[10000];
int merge_inversion(int a[], int low, int mid, int high)
{
int p = 0, i = low, j = mid + 1, cnt = 0;
int tmp[high - low + 1];
sort (a + low, a + mid);
sort (a + mid + 1, a + high);
while (i <= mid && j <= high)
{
if (a[i] > a[j])
{
tmp[p ++] = a[j];
cnt += (mid - i + 1);
//printf("%d\n", cnt);
j ++;
}
else
{
tmp[p ++] = a[i];
i ++;
}
}
if (i <= mid)
{
for (int k = i; k <= mid; k ++) tmp[p ++] = a[k];
}
else if (j <= high)
{
for (int k = j; k <= high; k ++) tmp[p ++] = a[k];
}
for (int k = 0; k < high - low + 1; k ++) a[low + k] = tmp[k];
//for (int i = 0; i < high - low + 1; i ++) printf("%d ", tmp[i]);
//printf("%d %d %d %d\n",low, mid, high, cnt);
return cnt;
}
int count_inversion(int a[], int low, int high)
{
int cnt = 0, mid;
if (low < high)
{
mid = low + (high - low) / 2;
cnt += count_inversion(a, low, mid);
cnt += count_inversion(a, mid + 1, high);
cnt += merge_inversion(a, low, mid, high);
}
return cnt;
}
int main ()
{
int n;
//vector<int> nums;
scanf("%d", &n);
for (int i = 0; i < n; i ++)
{
scanf("%d", &a[i]);
}
int ans = count_inversion(a, 0, n - 1);
printf("%d", ans);
return 0;
}
| 
转播
