三值的排序
分析
题目给出了目标状态,我们考虑向目标状态靠拢。
定义目标状态中的11...1
为1
区,22...2
为2
区,33...3
为3
区。
需要移动的第一种情况:x
在y
区且y
在x
区。操作数为1
。
需要移动的第二种情况:x
在y
区,y
在z
区,z
在x
区。操作数为2
。
求解:
设第一种情况的数量为A
,则
。
设第二种情况的数量为B
,则
。
其中S
为需要移动的数字的数量,
。
答案为A + 2B
。
实现
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n, a[N], b[N];
int cnt[4][4]; // cnt[i][j] 记录在 j 区的数字 i 的数量
int main () {
cin >> n;
for (int i = 1; i <= n; ++ i) cin >> a[i];
for (int i = 1; i <= n; ++ i) b[i] = a[i];
sort(b + 1, b + n + 1);
int b12 = -1, b23 = -1;
for (int i = 1; i <= n; ++ i) {
if (b12 == -1 && b[i] == 1 && b[i + 1] == 2) b12 = i;
if (b23 == -1 && b[i] == 2 && b[i + 1] == 3) b23 = i;
}
for (int i = 1; i <= b12; ++ i) ++ cnt[a[i]][1];
for (int i = b12 + 1; i <= b23; ++ i) ++ cnt[a[i]][2];
for (int i = b23 + 1; i <= n; ++ i) ++ cnt[a[i]][3];
int A = min(cnt[1][2], cnt[2][1])
+ min(cnt[1][3], cnt[3][1])
+ min(cnt[2][3], cnt[3][2]);
int S = cnt[1][2] + cnt[1][3] + cnt[2][1]
+ cnt[2][3] + cnt[3][1] + cnt[3][2];
int B = (S - 2 * A) / 3;
cout << A + 2 * B << endl;
return 0;
}