「UVA10810」Ultra-QuickSort 解题报告

题面

看不懂？！

大概的意思就是：

给出一个长度为n的序列，然后每次只能交换相邻的两个数，问最小需要几次使序列**严格上升 **

不断读入n，直到n=0结束

思路：

交换相邻的两个数，这不就类似冒泡排序吗？但是n<500000

算了吧，我回去颓A+B

于是我们就发现用冒泡排序直接计算次数是行不通的

但我们要知道：

冒泡排序的交换次数就是序列的逆序对数！！！

所以——就简单了吧~

如何求逆序对？

较easy版的逆序对

1、归并排序

思想是分治法

不断划分为两小段

然后依次由小序列合并为大序列，同时求出逆序数

2、树状数组

因为树状数组的修改查询是log级的所以可以使用（前缀和的方法），没学的建议先去学习一下，不是很难

Code：

#include<bits/stdc++.h>

#define ll long long

using namespace std;

struct node{

	int x,i;

}a[500010];

int n;

int b[500010];

int f[500010];

ll ans;

int read()

{

	int s=0;

	char c=getchar();

	while(!isdigit(c))

		c=getchar();

	while(isdigit(c))

	{

		s=(s<<1)+(s<<3)+c-'0';

		c=getchar();

	}

	return s;

}

void update(int x)//修改

{

	for(;x<=n;x+=x&(-x))

		f[x]++;

	return;

}

ll sum(int x)//求前缀和

{

	ll res=0;

	for(;x;x-=x&(-x))

		res+=f[x];

	return res;

}

bool cmp(node a,node b)

{

	return a.x>b.x;

}

int main()

{

	int i,j;

	n=read();

	while(n)

	{

		ans=0;

		memset(f,0,sizeof(f));

		for(i=1;i<=n;i++)

		{

			a[i].x=read();

			a[i].i=i;

		}

		sort(a+1,a+n+1,cmp);

		for(i=1;i<=n;i++)//先hash一下,按数值给其标记，方便后面求逆序对

			b[a[i].i]=i;

		for(i=1;i<=n;i++)

		{

			update(b[i]);//一步一做

			ans+=sum(b[i]-1);

		}

		printf("%lld\n",ans);

		n=read();

	}

	return 0;

}

巴特西

「UVA10810」Ultra-QuickSort 解题报告

题面

大概的意思就是：

思路：

如何求逆序对？

最新文章

热门文章