【文件属性】：
文件名称：逆序对问题
文件大小：1KB
文件格式：C
更新时间：2016-11-25 15:32:08
逆序对，算法
11087 统计逆序对
时间限制:1000MS 内存限制:65535K
提交次数:0 通过次数:0
题型: 编程题 语言: 无限制
Description
设a[0…n-1]是一个包含n个数的数组，若在ia[j]，则称(i, j)为a数组的一个逆序对（inversion）。
比如 <2,3,8,6,1> 有5个逆序对。
请考虑一个最坏情况O(nlogn)的算法确定n个元素的逆序对数目。
注意此题请勿用O(n^2)的简单枚举去实现。
并思考如下问题：
（1）怎样的数组含有最多的逆序对？最多的又是多少个呢？
（2）插入排序的运行时间和数组中逆序对的个数有关系吗？什么关系？
输入格式
第一行：n，表示接下来要输入n个元素，n不超过10000。
第二行：n个元素序列。
输出格式
逆序对的个数。
输入样例
5
2 3 8 6 1
输出样例
5
