题目大意：
排序是一种很频繁的计算任务。现在考虑最多只有三值的排序问题。一个实际的例子是，当我们给某项竞赛的优胜者按金银铜牌排序的时候。在这个任务中可能的值只有三种1，2和3。我们用交换的方法把他排成升序的。
写一个程序计算出，给定的一个1,2,3组成的数字序列，排成升序所需的最少交换次数。
解题思路：
// 复杂度 O(N^2)
// 先在输入的时候记录下1、2、3的个数，然后将在1部分的2和非1部分的1交换，接着是将在1部分的3和非1部分的1交换 （其中在1部分代表排完序之后在1所在的部分）
//最后是将在2部分的3 和在3部分的2 交换
// 先在输入的时候记录下1、2、3的个数，然后将在1部分的2和非1部分的1交换，接着是将在1部分的3和非1部分的1交换 （其中在1部分代表排完序之后在1所在的部分）
//最后是将在2部分的3 和在3部分的2 交换
int a[maxn], n, b[5], sum = 0;
void change(int x, int y, int st1, int st2) {
for (int i = st2; i < n; i++) if (a[i] == x) {
while(a[st1] != y) st1++;
if (st1 >= st2) break;
swap(a[st1], a[i]);
sum++;
}
}
int main ()
{
freopen ("sort3.in", "r", stdin);
freopen ("sort3.out", "w", stdout);
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", a + i);
b[a[i]]++;
}
change(1, 2, 0, b[1]);
// cout<<sum<<endl;
change(1, 3, 0, b[1]);
// cout<<sum<<endl;
change(2, 3, b[1], b[1] + b[2]);
cout<<sum<<endl;
return 0;
}
O(N)
(1, 2) (2, 1) / (1, 3) (3, 1) / (2, 3) (3, 2) 其中(a, b)在a的部分b的个数
上述三种只需要交换一次即可
剩下的就只有(1, 3) (3, 2) (2, 1) / (1, 2) (2, 3) (3, 1) 这两个需要交换两次
int a[maxn], part[4][4], n, b[4];
void get(int x, int st, int ed) {
for (int i = st; i < ed; i++) {
part[x][a[i]]++;
}
}
int main () {
freopen ("sort3.in", "r", stdin);
freopen ("sort3.out", "w", stdout);
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", a + i);
b[a[i]]++;
}
get(1, 0, b[1]);
get(2, b[1], b[1] + b[2]);
get(3, b[1] + b[2], n);
int sum = 0, one_two = 0, one_three = 0, two_three = 0;
one_two = min(part[1][2], part[2][1]);
one_three = min(part[1][3], part[3][1]);
two_three = min(part[2][3], part[3][2]);
// for (int i = 1; i <= 3; i++, cout<<endl) {
// for (int j = 1; j <= 3; j++)
// cout<<part[i][j]<<" ";
// }
int tot = n - part[1][1] - part[2][2] - part[3][3];
sum = one_two + one_three + two_three;
sum = sum + (tot - sum * 2) / 3 * 2;
cout<<sum<<endl;
return 0;
}