USACO Section2.1 Sorting a Three-Valued Sequence 解题报告

　　　　sort3解题报告 —— icedream61 博客园（转载请注明出处）
------------------------------------------------------------------------------------------------------------------------------------------------
【题目】
　　给你N，而后给出N个数，每个数都是1~3中的一个。请问，要把这个数列升序排好，最少需要进行几次两两交换？
【数据范围】
　　1<=N<=1000
【输入样例】
　　9
　　2
　　2
　　1
　　3
　　3
　　3
　　2
　　3
　　1
【输出样例】
　　4
------------------------------------------------------------------------------------------------------------------------------------------------
【分析】
　　模拟一遍最优策略，便可得出答案，具体做法如下：
　　　　1、读入N，并读入N个数d[1]~d[N]，定义最少所需交换次数s=0
　　　　2、统计下1~3分别的个数，得到1的个数num[1]和1、2的总个数num[2]。此时，便可确定最终1~3的位置分别是：
　　　　　　1: 1~num[1]
　　　　　　2: num[1]+1~num[2]
　　　　　　3: num[2]+1~N
　　　　3、第一轮交换，使所有的1都到位：
　　　　　　i=1~num[1]，找!=1的位置，不存在则不妨令i==num[1]+1
　　　　　　当i==num[1]+1则说明所有1均到位，本轮结束。否则，
　　　　　　j=num[1]+1~num[2]，找==1的位置，不存在则不妨令j==num[2]+1
　　　　　　k=num[2]+1~N，找==1的位置，不存在则不妨令j==N+1
　　　　　　能到这里说明需要交换一次，故而++S，
　　　　　　对当前i，首先争取一步换到位（即d[i]==2与d[j]换，或者d[i]==3与d[k]换），如不可能则找一个合法的换便可，不可能出现没有合法的换的情况。
　　　　4、第二轮交换，使所有的2都到位（3自然也就都到位了）：
　　　　　　i=num[1]+1~num[2]，找!=2的位置，不存在则不妨令i==num[2]+1
　　　　　　当i==num[2]+1则说明所有2均到位，本轮结束。否则，
　　　　　　j=num[2]+1~N，找==2的位置，不存在则不妨令j==N+1
　　　　　　能到这里说明需要交换一次，故而++S，
　　　　　　交换d[i]与d[j]。
　　　　5、至此，两轮交换完成，所得s即为最少所需交换次数。
------------------------------------------------------------------------------------------------------------------------------------------------
【总结】
　　开始没有注意到随便交换并非最优，没考虑到的就是分析中第3步的情况：在第一轮中应当先争取一步到位，这样可以减少一次交换次数。
　　本题还有个需要注意的地方（快排、二分等方法中也常出现这个问题），为了让下标不超出范围，要随时判断是否越界。

------------------------------------------------------------------------------------------------------------------------------------------------

【代码】

/*
ID: icedrea1
PROB: sort3
LANG: C++
*/

#include <iostream>
#include <fstream>
using namespace std;

int N,d[1001];
int num[4];

int main()
{
    ifstream in("sort3.in");
    ofstream out("sort3.out");

    in>>N;
    for(int i=1;i<=N;++i) { in>>d[i]; ++num[d[i]]; }
    num[2]+=num[1];

    // The situation of vector d:
    //  1: d[1]~d[num[1]]
    //  2: d[num[1]+1]~d[num[2]]
    //  3: d[num[2]+1]~d[N]

    int s=0;
    for(int i=1,j=num[1]+1,k=num[2]+1;;)
    {
        while(i<=num[1] && d[i]==1) ++i;
        if(i==num[1]+1) break;
        while(j<=num[2] && d[j]!=1) ++j;
        while(k<=N && d[k]!=1) ++k;
        ++s;
        if(d[i]==2 && j<=num[2]) swap(d[i],d[j]); else if(d[i]==3 && k<=N) swap(d[i],d[k]); // 一步换到位更优
        else if(j<=num[2]) swap(d[i],d[j]); else swap(d[i],d[k]); // 无法一步到位，那就换个合法的就行
    }
    for(int i=num[1]+1,j=num[2]+1;;)
    {
        while(i<=num[2] && d[i]==2) ++i;
        if(i==num[2]+1) break;
        while(j<=N && d[j]!=2) ++j;
        swap(d[i],d[j]); ++s;
    }

    out<<s<<endl;

    in.close();
    out.close();
    return 0;
}