兩個(gè)數(shù)，如果它們現(xiàn)在的位置和最終排序后的位置恰好相反，那么將這兩個(gè)數(shù)互換，就不需要再動(dòng)了。對于這樣的數(shù)，互換次數(shù)為1。
除此之外，可能是1在2的位置上，2在3的位置上，3在1的位置上或1在3的位置上，3在2的位置上，2在1的位置上。這樣形成一個(gè)環(huán)。這個(gè)環(huán)換2次，即可排好序。
首先用計(jì)數(shù)排序計(jì)算好某一個(gè)數(shù)應(yīng)該在的位置，然后分別計(jì)算出上面兩種情形的數(shù)目。相加即可。
#include?<iostream>
#include?<fstream>
using?namespace?std;
ifstream?fin("sort3.in");
ofstream?fout("sort3.out");
#ifdef?_DEBUG
#define?out?cout
#define?in?cin
#else
#define?out?fout
#define?in?fin
#endif
//?sum[i]：i的最終位置為sum[i-1]->sum[i]之間
int?sum[4];
//?cnt[i][j]?i位置上j的數(shù)目
int?cnt[4][4];?
//存儲(chǔ)原始輸入數(shù)據(jù)
int?data[1000];
//排好序后，第i個(gè)位置應(yīng)該是什么數(shù)
int?get_num(int?i)
{
????if(i<=sum[1])?return?1;
????else?if(i<=sum[2])?return?2;
????else?return?3;
}
void?solve()
{
????int?n;
????in>>n;
???
????int?tmp;
????for(int?i=0;i<n;++i){
????????in>>data[i];
????????sum[?data[i]?]?++;
????}
????sum[2]+=sum[1];
????sum[3]+=sum[2];
????for(int?i=0;i<n;++i){
????????cnt[get_num(i+1)][data[i]]++;
????}
????int?res?=?0;
????for(int?i=1;i<=3;++i){
????????for(int?j=1;j<=3;++j){
????????????if(i==j)?continue;
???????????tmp?=?min(cnt[i][j],cnt[j][i]);
???????????cnt[i][j]-=tmp;
???????????cnt[j][i]-=tmp;
???????????res+=tmp;
????????}
????}
????res+=min(cnt[2][3],min(cnt[3][1],cnt[1][2]))*2;
????res+=min(cnt[2][1],min(cnt[3][2],cnt[1][3]))*2;
????out<<res<<endl;
}
int?main(int?argc,char?*argv[])
{
????solve();?
????return?0;
}