USACO 2.1.3 Sorting a Three-Valued Sequence（sort3）

这道题就是给出由123三个值的一个数字序列，然后让你把这个序列升序排序，求最小的交换次数。注意这里可以不是相邻交换。

刚开始一看题的时候，还以为t=a a=b b=t那种水题呢，然后发现不是水题。。

于是就想思路...既然是排序题，就先把他排序好了，然后就再对比一下。

比如说USACO上的样例数据：

排序前排序后

(1)2 1
(2)2 1
(3)1 2
(4)3 2
(5)3 2
(6)3 3
(7)2 3
(8)3 3
(9)1 3

既然他要求的是最少次数，那么我们就不要移动已经在原位不用移动的数据，所以我们可以把在原位不用移动的数据删掉。这里的6和8是不用移动的数据。删掉后，然后变成了：

(1)2 1
(2)2 1
(3)1 2
(4)3 2
(5)3 2
(7)2 3
(9)1 3

这就出现可以两两交换的位置了，比如说第1号位置和第3号位置可以两两交换。我们把可以两两交换的位置定义为交叉相等。这个数据里面的第1号和第3号是交叉相等，第3号和第7号是交叉相等的，所以把他们两两交换就能回到原位了。两两交换只会交换一次，所以在这一步里面，把答案每交换一次+1，直到没有再能两两交换的位置了。然后就变成了：

(2)2 1
(5)3 2
(9)1 3

我们发现这里就剩下三组了，其实每一组数据筛选之后都会变成3的倍数组。想一想为什么。因为他这里面一共会出现3种数据（1,2,3），而会出现第一次筛选出现的在原位的情况，第二次筛选出现的互相换的情况，这次该出现三数据交换的情况了。为什么不会出现四个数据交换？因为他只有三个数据，你第四个数据哪里蹦出来的。。。既然剩下的都是三个数据交换，那么就不用再次寻找了，可以用剩余数据总数直接计算了。因为每一对三数据换会换两次（自己试试就知道了），所以这一次需要交换的次数为(剩余组数/3*2)。

既然思路理清了，就上代码把。。

解释一下，a是输入的数组，b是排序后的数组，c是是否被排除，没排除就是0，被排除就是1。

n是输入的数据总数，m是剩余的数据总数（会不断减少）。ans就是答案，就是交换的总次数。

/*

ID:aaabbbr1

LANG:C++

TASK:sort3

*/

#include <stdio.h>

#include <string.h>

#include <algorithm>

using namespace std;

int a[1002];

int b[1002];

bool c[1002];

int main()

{

	freopen("sort3.in","r",stdin);

	freopen("sort3.out","w",stdout);

	int n,m;

	scanf("%d",&n);

	m=n;//刚开始的时候，剩余数据数等于数据总数

	int ans=0;//答案要是0

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

	{

		scanf("%d",&a[i]);

		b[i]=a[i];//b数组是用来排序的

	}

	sort(b+1,b+1+n);//排序b数组

	memset(c,0,sizeof(c));//c数组是用来标识是否被排除的

	for(int i=1;i<=n;i++)//枚举一个换的情况

	{

		if(a[i]==b[i])//如果数据在原位

		{

			m--;//剩余数据数-1

			c[i]=1;//排除数据

		}

	}

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

	for(int j=1;j<i;j++)//穷举两个互换的情况
	{

		if(a[i]==b[j]&&a[j]==b[i]&&c[i]!=1&&c[j]!=1)//意思是如果符合交叉相等并且两个都未被排除

		{

			m-=2;//数据剩余数减去2

			ans+=1;//答案+1，需要交换一次

			swap(a[i],a[j]);//这句好像没必要

			c[i]=1;//排除，否则出错

			c[j]=1;//同上

		}

	}

	ans+=m/3*2;//这是3个换的情况

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

	fclose(stdin);

	fclose(stdout);

	return 0;

}

巴特西

USACO 2.1.3 Sorting a Three-Valued Sequence（sort3）

最新文章

热门文章