這道題目是做的比較順利的一道。
雖說題目上要求交換，但實際上并不需要交換的具體配對。也就是說，隻要通過計數，就可以完成交換次數的計算。另外，因為題目數值範圍隻有123，是以連排序本身也可以通過計數來完成。
實際的思路是這樣的，先對123分别的個數進行計數，這樣就能知道每段的個數。由每段的個數，統計出每段需要交換、要交換到哪裡去的個數。統計完成之後，優先計算可以直接交換的對數，剩下的就是需要交換兩次的。
這段算法講起來很累，其實畫個草圖說明下就清楚了：
比如說這道題的原始資料是：
9
2
2
1
3
3
3
2
3
1
這段資料中1的個數是2，2的個數是3，3的個數是4。
下圖的第1列是原始資料，我對123應該的位置用藍線劃開了。
對于第一段來說，兩個2都不在應該的位置，是以有由1向2交換的兩個需求。第二段的第一個，可以标記為由2向1交換的一個需求。以此類推。
将需求的數量進行一個統計，最終得出的一個矩陣是這樣的，這是對第一張表第2列的一個歸納，我們需要做的是把标黃的格子最終都變成0：
其中，由于交換次數越少越好，可以優先交換的是第1行第2列與第2行第1列、第1行第3列與第3行第1列、第2行第3列與第3行第2列，這三組。
刨去直接交換的配對之後，表格變成了這樣：
| 1 | |
| 1 | |
| 1 | 2 |
也就是說，第1段中還有一個2，第2段有1個3，第3段有一個1。這樣的話，需要調換兩次，就能使排序完成。
每組不能直接交換的組合，都會在标黃格子中增加共計3。是以集中統計最後的餘量，就可以得到最終的交換次數。
附上代碼：
#include <iostream>
#include <fstream>
using namespace std;
int N;
const int MAXDATA = 1001;
int data[MAXDATA];
int ex[4][4];
int cnt = 0;
int rmnd = 0;
int main()
{
ifstream fin ("sort3.in");
ofstream fout ("sort3.out");
int i;
fin >> N;
for (i = 0; i < N; i ++) {
fin >> data[i];
ex[0][data[i]] ++;
}
for (i = 0; i < ex[0][1]; i ++)
ex[1][data[i]] ++;
for (i = ex[0][1]; i < ex[0][1] + ex[0][2]; i ++)
ex[2][data[i]] ++;
for (i = ex[0][1] + ex[0][2]; i < N; i ++)
ex[3][data[i]] ++;
cnt += ex[1][2] < ex[2][1] ? ex[1][2] : ex[2][1];
rmnd += ex[1][2] < ex[2][1] ? ex[2][1] - ex[1][2] : ex[1][2] - ex[2][1];
cnt += ex[2][3] < ex[3][2] ? ex[2][3] : ex[3][2];
rmnd += ex[2][3] < ex[3][2] ? ex[3][2] - ex[2][3] : ex[2][3] - ex[3][2];
cnt += ex[1][3] < ex[3][1] ? ex[1][3] : ex[3][1];
rmnd += ex[1][3] < ex[3][1] ? ex[3][1] - ex[1][3] : ex[1][3] - ex[3][1];
cnt += rmnd/3*2;
fout << cnt << endl;
return 0;
}
我稍微看了一下官方解，我的算法跟第三種基本一樣，它在計算餘量的時候比我要更進一步。嗯，這道題就這樣做好了。
說句閑話，這道題中第一段關于三鍵值排序的描述，我實在沒看出來跟做題有什麼關系，以為自己了解錯了題意愣了半天……