分治题目 wikioi 1688 逆序数组 算导2-4

解题报告

算导上给了提示 用归并排序的代码进行修改来实现 思考后不难看出 归并排序的合并(merge)过程中 对数据进行了比较

1）如果数组L 的当前某元素大于数组R的当前元素，那么 由于L数组是有序的(升序) 因此 L数组当前元素以及他后面的所有元素都与R数组构成逆序对

2）我们的排序并不影响逆序对的数量 因为排序的时候不会改变当前被排序的数据和还未被处理的数据之间的位置关系(就是说 排序前在未处理元素左边的数据，排序后还在未处理元素左边，所以不改变逆序对的数量) 

严格的证明待以后学好算法导论再来证，现在只要知道上面两条就可以来处理这道题了

最初的时候 由于把deseq技术变量设为了 int 导致溢出  结果WA了 后来用随机数据测试之后 找到了问题 改为了long long

真的是好久不写题了，连最低级的错误都犯

修改归并排序的merge代码

/*************************************************************************
  > File Name: mergesort.cpp
  > Author: VOID_133
  > QQ: 393952764
  > Mail: zhangjianqiu13@gmail.com 
  > Created Time: 2014年08月06日 星期三 14时17分16秒
  > Content : Divide and Conquer Classic Problem 
  MergeSort
 ************************************************************************/

#include<iostream>
#include<cstdio>
typedef long long LL;
using namespace std;
const int MAX=100000;
int L[MAX];
int R[MAX];
LL deseqnum=0;
void mergesort(int* A,int first,int end);
void merge(int *A,int first,int mid,int end);
void mergesort(int* A,int first,int end)
{
	if(first<end)
	{
		int mid=(first+end)/2;		
		mergesort(A,first,mid);			 
		mergesort(A,mid+1,end);	//Solve the problem recursively
		merge(A,first,mid,end);
	}
	return ;
}

void merge(int *A,int first,int mid,int end)
{
	int lenL=mid-first+1;
	int lenR=end-mid;
	for(int i=1;i<=lenL;i++) L[i]=A[first+i-1];
	for(int i=1;i<=lenR;i++) R[i]=A[mid+i];
	int li=1;
	int ri=1;
	int cnt=first;						//the array we should merge is from A[first] to A[end] so we can only modify these value ,we shouldn'tmodify other A values
	//The Problem has fixed
	while(li<=lenL && ri <=lenR)
	{
		int tmp;
		if(L[li]>R[ri])
		{
			tmp=R[ri];
			ri++;
			deseqnum+=lenL-li+1;                                //这个代码是后来添加的逆序对计数代码 其余的代码都没有改动
		}
		else
		{
			tmp=L[li];
			li++;
		}
		A[cnt++]=tmp;
	}
	if(li<=lenL)
	{
		while(li<=lenL)
		{
			A[cnt++]=L[li++];	
			//deseqnum+=lenR;
		}
		//deseqnum-=lenR;
	}
	while(ri<=lenR)
	{
		A[cnt++]=R[ri++];
	}
	return ;
}


int main(void)
{
	int arr[MAX];
	int n;
	while(	scanf("%d",&n)!=EOF)
	{
		deseqnum=0;
		for(int i=1;i<=n;i++) cin>>arr[i];
		mergesort(arr,1,n);
		//for(int i=1;i<=n;i++) cout<<arr[i]<<" ";
		cout<<deseqnum<<endl;
	}

	return 0;
}    

某人的blog这么说：

该算法若将合并数组操作写成循环形式会快百分之二十到三十，因为递归调用函数时会占用额外的时间。

wikiOI的题解上说此题可以用线段树来做ORZ 还有树状数组ORZ   慢慢来吧Orzzzzzzzzzzzzzzzzzzzzzzzzzz