最少交换次数

分数 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）。