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

解析

这是道贪心题，因为是求最少的交换次数，所以我们的每次交换都要最有价值。
Size数组记录123各自的数量，这样我们就知道123应该在哪些位置。
最有价值的交换是怎样的呢？ 比如2在1的位置，而在2的位置里恰好有1，那么交换这两数字
会让两者同时归位。
不停地重复如此操作到最后会有两种情况，一是完全归位，二是仍有几个数无法归位，例如2-3-1
或者2-2-3-3-1-1。易知形如231只需两步交换可归位。

---

代码

#include <iostream>
#include <cstdio>
#include <fstream>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;
int n,m,k;
int cot[1001],Size[4],Pos[5];// Pos记录123的起始位置 4是末尾

int main(void){

    cin>>n;

    for(int i=0;i<n;i++){
        cin>>cot[i];
        Size[ cot[i] ] ++;
    }
    for(int i=1;i<=4;i++) Pos[i]=Pos[i-1]+Size[i-1];

    int ans = 0;
    for(int i=1;i<3;i++){
        for(int a=Pos[i]; a<Pos[i+1]; a++){
            if( cot[a] != i ){
                for(int b=Pos[ cot[a]  ];b<Pos[cot[a]+1];b++)
                    if( cot[b] == i ){
                        swap(cot[a],cot[b]);
                        ans++;
                        break;
                }
            }
        }
    }

    int aft =0;
    for(int i=1;i<4;i++){
        for(int a=Pos[i]; a<Pos[i+1]; a++){
            if( cot[a] != i ) aft++;

        }
    }
    if(aft % 3 == 0) ans+=2*(aft/3);

    cout<<ans<<endl;
    return 0;
}