2.1.3 Sorting a Three-Valued Sequence 三值的排序
时间： 1ms 内存：64M
描述：
排序是一种很频繁的计算任务。现在考虑最多只有三值的排序问题。一个实际的例子是，当我们给某项竞赛的优胜者按金银铜牌序的时候。
在这个任务中可能的值只有三种1，2和3。我们用交换的方法把他排成升序的。
写一个程序计算出，给定的一个1,2,3组成的数字序列，排成升序所需的最少交换次数。
输入：
Line 1:
N (1 <= N <= 1000) Lines 2-N+1: 每行一个数字，共N行。（1..3）
输出：
共一行，一个数字。表示排成升序所需的最少交换次数。
示例输入：
9
2
2
1
3
3
3
2
3
1
示例输出：
4提示：
参考答案（内存最优[752]）：
#include<stdio.h>
#define MAX 1002
int a[MAX],b[4]={0},c[4]={0};
int n;
int main()
{
int i,j,count;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
b[a[i]]++;
}
for (i=0;i<b[1]+b[2];i++){
if (a[i]==3) c[3]++;
else if (a[i]==2&&i<b[1]) c[1]++;
else if (a[i]==1&&i>=b[1]) c[2]++;
}
printf("%d\n",c[3]+(c[1]>c[2]?c[1]:c[2]));
return 0;
}
参考答案（时间最优[0]）：
/*
ID: ayludon3
PROG: sort3
LANG: C++
*/
#include <fstream>
#include <iostream>
#include <string.h>
#include <math.h>
using namespace std;
int abs(int a)
{
if(a>0)
return a;
else
return (-1*a);
}
int main()
{
// ifstream cin("sort3.in");
// ofstream cout("sort3.out");
int n,i,res;
int p[1005],num[4],wrong[4];
cin>>n;
res=0;
memset(num,0,sizeof(num));
memset(wrong,0,sizeof(wrong));
for(i=1;i<=n;i++)
{
cin>>p[i];
num[p[i]]++;
}
//wrong[3]=C31+C32(3放在1、2位置上的个数)
//wrong[2]=B21(2放在1位置上的个数)
//wrong[1]=A12(1放在2位置上的个数)
for(i=1;i<=num[1]+num[2];i++)
{
if(p[i]==3)
wrong[3]++;
else if(p[i]==2&&i<=num[1])
wrong[2]++;
else if(p[i]==1&&i>num[1])
wrong[1]++;
}
//3放在1、2位置上的全部调走，另外加上A12和B12互换，再加上A12和B21的差
//即res=wrong[3]+min(wrong[1],wrong[2])+abs(wrong[1]-wrong[2])=wrong[3]+max(wrong[1],wrong[2])
res=wrong[3]+min(wrong[1],wrong[2])+abs(wrong[1]-wrong[2]);
cout<<res<<endl;
return 0;
}
题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。