Home > Old Blog Posts > USACO 2.1.3 Sorting a Three-Valued Sequence

USACO 2.1.3 Sorting a Three-Valued Sequence


这道题方法一大把。

究其本质,其实就是不做无用的交换。

我在之前的题解中曾给出这样一种方法:

输入数据记录到数组a,生成排好序的数组b,然后开始循环。每次寻找a[i]与b[i]不相等的,先查找是否存在一个a[j],使得a[i]与a[j]交 换后都能到自己正确的位置上;再查找是否存在a[j]使a[i]与a[j]交换后至少一个能到正确的位置;若两者都没有,则取最前面的一个a[j]和 b[j]不相等的进行交换。每次交换次数+1。
最后统计次数输出。

从叙述的字数已经可以看出,这种方法比较麻烦。

分析题目特点,要排序的数字只有1,2,3。从另外的角度出发,设一个已经排好序的数组b(想象就行了..),我们用一个数组m来统计每一段中每个数字出现的次数,拿样例来说吧:

2 2 1 3 3 3 2 3 1 (原始)

1 1 2 2 2 3 3 3 3 (已排序)

那么

m[1][1]=0

m[1][2]=2

m[1][3]=0

….

利用这个数组我们可以产生出许多的方法……

比如我用的是:ans=m[2][1]+m[3][1]+m[2][3]+max(0,m[1][3]-m[3][1])

啥意思呢?先把1放好,再把3放好,那2就自然放好了。放1只要把2和3中的1挪到前面,是m[2][1]+m[3][1]次;放3则要先把2中的3挪到后面,是m[2][3]次,再把1中的3挪到后面,注意,放1的时候已经有部分3进行了交换,这一部分应该被减去,因此是max(0,m[1][3]-m[3][1])。

此外还有很多方法,但本质都是一样的(一开始就说了),此处不再一一叙述。

代码:

/*
ID: dementr1
PROG: sort3
LANG: C++
*/
#include<iostream>
#include<fstream>
using namespace std;
ifstream fin(“sort3.in”);
ofstream fout(“sort3.out”);
int a[1001],m[4][4],n,x,y,z,ans;
void init()
{
fin>>n;
for(int i=0;i<n;i++)
{
fin>>a[i];
if(a[i]==1) x++;
if(a[i]==2) y++;
if(a[i]==3) z++;
}
}
void work()
{
int i;
for(i=0;i<x;i++)
m[1][a[i]]++;
for(i=x;i<x+y;i++)
m[2][a[i]]++;
for(i=x+y;i<x+y+z;i++)
m[3][a[i]]++;
ans=m[2][1]+m[3][1]+m[2][3]+max(0,m[1][3]-m[3][1]);
}
int main()
{
int i,j,t;
init();
work();
fout<<ans<<endl;
return 0;
}

Categories: Old Blog Posts
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: