题目链接:
题意:
多组案例,先输入数据的数目,在依次输入数据,判断将这些数据从小到大排列最少需要多少操作步数。(案例以输入0结束)
案例:
Sample Input
5
9
1
0
5
4
3
1
2
3
0
Sample Output
6
0
分析:这一题我参考了一位大神的思路分析,觉得讲解挺详细的,也给了我做题思路,所以借鉴了过来。具体如下:
题目本质就是求逆序对了,简单介绍一下。逆序对是指在序列 {a0,a1,a2...an}中,若ai<aj(i>j),则(ai,aj)上一对逆序对。而逆序数顾名思义就是序列中逆序对的个数。例如: 1 2 3是顺序,则逆序数是0;1 3 2中(2,3)满足逆序对的条件,所以逆序数只有1; 3 2 1中(1,2)(1,3)(2,3)满足逆序对,所以逆序是3。由定义不能想象,序列n的逆序数范围在[0,n*(n-1)/2],其中顺序时逆序数为 0,完全逆序时逆序数是n*(n-1)/2。
可以利用归并排序时计算逆序个数,时间复杂度是nlog2n,而空间复杂度 2n。 利用归并求逆序是指在对子序列s1和s2在归并时,若s1[i]>s2[j](逆序状况),则逆序数加上s1.length-i,因为s1 中i后面的数字对于s2[j]都是逆序的。具体看注释吧。
归并算法基本思路
设两个有序的子文件放在同一向量中相邻的位置上:R[low..m],R[m+1..high],先将它们合并到一个局部的暂存向量R1中,待合并完成后将R1复制回R[low..high]中。
合并过程中,设置i,j和p三个指针,其初值分别指向这三个记录区的起始位置。合并时依次比较R[i]和R[j]的关键字,取关键字较小的记录复制到R1[p]中,然后将被复制记录的指针i或j加1,以及指向复制位置的指针p加1。
重复这一过程直至两个输入的子文件有一个已全部复制完毕(不妨称其为空),此时将另一非空的子文件中剩余记录依次复制到R1中即可。
源代码:
1 #include2 #define MAX 500001 3 int a[MAX], b[MAX],i; 4 long long ans; 5 void merge(int l,int m,int r)//归并 6 { 7 int p=0,i=l,j=m+1;//p指向输出,i,j指向输入 8 while(i<=m&&j<=r)//两个输入空间不为0 9 {10 if(a[i]>a[j])//取最小值转入输出空间11 {12 b[p++]=a[j++];13 ans+=m-i+1;//a[i]后数值相对于a[i]为逆序14 }15 else16 b[p++]=a[i++];17 }18 while(i<=m) b[p++]=a[i++];//非空输入空间转入输出空间19 for(i=0;i