C++逆序对

 

代码模板

typedef long long LL
LL merge(int l,int r)
{
	if(l==r) return 0;
	int mid=l+r>>1;
	LL ans = merge(l,mid)+merge(mid+1,r);
	
	int i=l,j=mid+1,cnt=0;
	while(i<=mid&&j<=r)
	{
		if(q[i]<=q[j]) tmp[cnt++]=q[i++];
		else
		{
			tmp[cnt++]=q[j++];
			ans+=mid-i+1;
		}
	}//统计
	//扫尾
	while(i<=mid) tmp[cnt++]=q[i++];
	while(j<=r) tmp[cnt++]=q[j++];
	//扫描完毕
	for(i=l,j=0;i<=r;i++,j++) q[i]=tmp[j];
	return ans;
}

代码原理

归并排序

​ 逆序需要的是判断前面数字比后面大的时候组成一个逆序对,而为了扫描的过程中只扫描一部分,不全部扫描即可得出答案,达到优化的目的,这里采用归并排序的思路,在分为A和B两组数组的同时,如果判断到了A中有一个数字比B中另外一个数字大的话,就可以很肯定的判断A之后的数字和该小的B数字都可以组成逆序对,因此可以达到简化运算量的效果。

注意

  1. 对于结束的情况返回return 0
  2. 由于分治的过程中十分有可能出现代码规模超过int的情况,所以这里会使用long long进行数据的定义。
  3. 由于等于的情况并不算逆序对,所以在判断if的时候要把等于号带上
  4. 通过先对最原始的”大片段“进行计算逆序对的数量,然后逐渐细化扫描更小的逆序对的数量,在扫描到return之后加起来返回的就是整个数列全部情况的逆序对的总数了。