算法 12. 变换砖头

 #include <stdio.h>//这是第十二题 变换砖头 
long long int bricks[300002];//定义一个数组来存放初始时砖的高度，需要把数组定义在主函数之外。 
long long int sorted_bricks[300002];//再定义一个数组来暂时存放排序好的砖，最后再导回到bricks里面 
long long count=0;//计数器，来记录有多少个逆序对 


void mergesort(long int left,long int right,long long int bricks[],long long int sorted_bricks[])//在这里定义归并排序的函数，略作修改来求逆序对。 
{
	if(right-left>0)//如果此时的待排序部分不为空，则继续 
	{
		long int middle=(left+right)/2;//首先尽量从中间阶段，进行下一步的归并操作 
		long int i=left;//保存左边的位置 
		long int p=left,q=middle+1;//保存中间的位置 
		mergesort(left,middle,bricks,sorted_bricks);//将此数列再分成两个子数列进行归并 
		mergesort(middle+1,right,bricks,sorted_bricks);//（这里对了就很奇怪，因为之前用快排的时候也是这样的递归写法，但是排出的结果是错误的） 
        while(p<=middle||q<=right)//排序的具体操作，两个子数列只要有一个为空，就继续填入，在此之前不断选出较小的来填入 
        {
            if(q>right||(p<=middle&&bricks[p]<=bricks[q]))
                sorted_bricks[i++] = bricks[p++];
            else
            {
                sorted_bricks[i++] = bricks[q++];
                count=count+middle-p+1;
            }
        }
        for(i = left; i <= right; i++)//将sorted_bricks中排好序的元素复制到bricks中
            bricks[i]=sorted_bricks[i];
    }
}
int main()
{
	long int n;
	scanf("%ld",&n);
	for(long int i=0;i<n;i++)
	{
		scanf("%lld",&bricks[i]);
	}//存放砖的状态
	//本题的思路是用归并排序求逆序对
	mergesort(0,n-1,bricks,sorted_bricks);//这里和讨论区里给出的归并算法不一样的是，C语言中需要把数组作为参数传入函数中。 
	printf("%ld\n",count);
	return 0;
}