# 2.1.3 Sorting a Three-Valued Sequence 三值的排序

2.1.3 Sorting a Three-Valued Sequence 三值的排序

Line 1:
N (1 <= N <= 1000) Lines 2-N+1: 每行一个数字，共N行。（1..3）

``````9
2
2
1
3
3
3
2
3
1
``````

``4``

``````#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;
}
``````

``````/*
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;
}
``````