首先讀入數(shù)組，將數(shù)組和排好序的數(shù)組進(jìn)行比較，nij表示應(yīng)該在i的地方放置的是j的個(gè)數(shù)。
先將1放入應(yīng)該在的位置，需要n12+n13次交換，然后將3放入應(yīng)該在的位置，注意，n13中一些3被交換到2或者在處理1的時(shí)候已經(jīng)交換到3，所以交換3就是n23+max(0,n13-n31).
/*
ID:Ryan
PROG:sort3
LANG:C++
*/
#include <iostream>
#include <fstream>
#include <memory.h>
#include <cmath>
#include <algorithm>
using namespace std;
ifstream fin ("sort3.in");
ofstream fout ("sort3.out");
int main()
{
ifstream fin ("sort3.in");
ofstream fout ("sort3.out");
int a[1001];
int nn[4]={0,0,0,0};
int n13=0,n23=0,n12=0,n31=0,n32=0,n21=0;
int i,sum=0,n;
fin>>n;
for(i=1;i<=n;i++)
{
fin>>a[i];
nn[a[i]]++;
}
for(i=1;i<=nn[1];i++)
{
if(a[i]==2) n12++;
if(a[i]==3) n13++;
}
for(i=nn[1]+1;i<=nn[1]+nn[2];i++)
{
if(a[i]== 1) n21++;
if(a[i]== 3) n23++;
}
for(i=nn[1]+nn[2]+1;i<=n;i++)
{
if(a[i]== 1) n31++;
if(a[i]== 2) n32++;
}
int t;
fout<<n21+n31+n23+max(0,n13-n31)<<endl;
//system("PAUSE");
return 0;
}