【文件属性】:
文件名称:逆序对问题
文件大小:1KB
文件格式:C
更新时间:2016-11-25 15:32:08
逆序对,算法
11087 统计逆序对
时间限制:1000MS 内存限制:65535K
提交次数:0 通过次数:0
题型: 编程题 语言: 无限制
Description
设a[0…n-1]是一个包含n个数的数组,若在i
a[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