欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

算法 12.变换砖头

程序员文章站 2024-03-23 09:18:34
...

算法 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;
}