最少交換次數

分數 15

作者?計科G隊長

單位?重慶大學

長度為N的數組中只有1，2，3三種值，要按升序排序，并且只能通過數值間的兩兩交換實現不能移位。比如某項競賽的優勝者按金銀銅牌排序，或者荷蘭國旗問題都是該問題的實例。給定的一個 1,2,3 組成的數字序列，求排成升序所需的最少交換次數。

輸入格式:

Line 1: N?(1≤N≤1000)
Lines 2--(N+1): 每行一個數字1，2或3，共 N 行。

輸出格式:

共一行，一個數字，表示排成升序所需的最少交換次數。

輸入樣例:

在這里給出一組輸入。例如：

9
2
2
1
3
3
3
2
3
1 

輸出樣例:

共一行,一個數字.表示排成升序所需的最少交換次數.

4

#include <bits/stdc++.h>
using namespace std;signed main() {int N;cin >> N;vector<int> arr(N);int c1 = 0, c2 = 0, c3 = 0;for (int i = 0; i < N; ++i) {cin >> arr[i];if (arr[i] == 1) c1++;else if (arr[i] == 2) c2++;else c3++;}int e12 = 0, e13 = 0, e21 = 0, e23 = 0, e31 = 0, e32 = 0;// 1區: 0 to c1-1for (int i = 0; i < c1; ++i) {if (arr[i] == 2) e12++;else if (arr[i] == 3) e13++;}// 2區: c1 to c1 + c2 -1for (int i = c1; i < c1 + c2; ++i) {if (arr[i] == 1) e21++;else if (arr[i] == 3) e23++;}// 3區: c1 + c2 to N-1for (int i = c1 + c2; i < N; ++i) {if (arr[i] == 1) e31++;else if (arr[i] == 2) e32++;}int s1 = min(e12, e21);int s2 = min(e13, e31);int s3 = min(e23, e32);int total_errors = e12 + e13 + e21 + e23 + e31 + e32;int remaining = total_errors - 2 * (s1 + s2 + s3);int swaps = s1 + s2 + s3 + remaining / 3 * 2;cout << swaps << endl;return 0;
}

為了計算最少交換次數，我們可以考慮以下幾點：

1. 分區統計：首先，統計數組中1、2、3的個數。假設有c1個1，c2個2，c3個3。那么排序后的數組應該是前c1個是1，接著c2個是2，最后c3個是3。

2. 錯誤放置的元素：在排序后的數組中，每個分區（1區、2區、3區）中不應該有其他分區的元素。例如，1區中不應該有2或3，2區中不應該有1或3，3區中不應該有1或2。

3. 交換策略：

   • 1區中的非1元素：1區中的2或3需要被交換出去。理想情況下，我們可以將1區中的2與2區中的1交換，或者1區中的3與3區中的1交換。這樣可以一次交換糾正兩個錯誤。

   • 2區中的非2元素：類似地，2區中的1可以與1區中的2交換，2區中的3可以與3區中的2交換。

   • 3區中的非3元素：同樣處理。

4. 計算最少交換次數：

最少交換次數 = （可以直接交換的對數） + 2 * （剩下的無法直接交換的錯誤數）/ 3

1. 首先，計算每個分區中錯誤放置的元素數量。

2. 對于可以互相交換的錯誤（如1區中的2和2區中的1），每次交換可以糾正兩個錯誤，因此這樣的交換次數是min(1區中的2, 2區中的1)。

3. 剩下的錯誤需要通過每是那個需要通過兩次交換來糾正一個錯誤（例如，1區中的2、2區中的3、3區中的1）。