最少交换次数

分数 15

作者計科G隊長

单位重庆大学

长度为N的数组中只有1，2，3三种值，要按升序排序，并且只能通过数值间的两两交换实现不能移位。比如某项竞赛的优胜者按金银铜牌排序，或者荷兰国旗问题都是该问题的实例。给定的一个 1,2,3 组成的数字序列，求排成升序所需的最少交换次数。

输入格式:

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

输出格式:

共一行，一个数字，表示排成升序所需的最少交换次数。

输入样例:

在这里给出一组输入。例如：

输出样例:

共一行,一个数字.表示排成升序所需的最少交换次数.

#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、2、3的个数。假设有c1个1，c2个2，c3个3。那么排序后的数组应该是前c1个是1，接着c2个是2，最后c3个是3。
错误放置的元素：在排序后的数组中，每个分区（1区、2区、3区）中不应该有其他分区的元素。例如，1区中不应该有2或3，2区中不应该有1或3，3区中不应该有1或2。
交换策略：
- 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元素：同样处理。
计算最少交换次数：