#3945. 求逆序对数
求逆序对数
【问题描述】
对于一个长度为N的整数序列A,满足i < j 且 Ai > Aj的数对(i,j)称为整数序列A的一个逆序。
请求出整数序列A的所有逆序对个数。
【输入形式】
输入包含多组测试数据,每组测试数据有两行,
第一行为整数N(1 <= N <= 20000),当输入0时结束,
第二行为N个整数,表示长为N的整数序列。
【输出形式】
每组数据对应一行,输出逆序对的个数。
【样例输入】
5
1 2 3 4 5
5
5 4 3 2 1
1
1
0
【样例输出】
0
10
0
分析
直接暴力遍历的话,算法复杂度肯定到O ( n 2 ) O(n^2)O(n 2 )
结合分治和归并排序的思想
我们可以将求一个序列的逆序数,转换为求左右两个序列的逆序数相加,同时进行从小到大的排序
而一个序列的逆序数怎么求?因为此序列已经由子序列递归得到,左右序列在各自的内部已经由小到大有序,分别从各自的第一个数开始比较,如果出现第一组的数大于第二组的数,那么第一组后面的数肯定大于第二组此时的数。
举个例子:对于1 , 3 , 4 , 5 , 2 , 6 , 7 , 8 1,3,4,5,2,6,7,81,3,4,5,2,6,7,8,所以1 , 3 , 4 , 5 1,3,4,51,3,4,5是A,2 , 6 , 7 , 8 2,6,7,82,6,7,8是B组,可以看出组内已经有序,
比较1和2,1<2,不统计,A组后移1个数 比较3和2,3>2,所以逆序对+3(第一组后面还有3个数),B组后移1个数 比较3和6,……
Limitation
1s, 1024KiB for each test case.