三值的排序

分析

题目给出了目标状态，我们考虑向目标状态靠拢。

定义目标状态中的11...1为1区，22...2为2区，33...3为3区。

需要移动的第一种情况：x在y区且y在x区。操作数为1。

需要移动的第二种情况：x在y区，y在z区，z在x区。操作数为2。

求解：

设第一种情况的数量为A，则

$A = m i n (c n t [1] [2], c n t [2] [1]) + m i n (c n t [1] [3], c n t [3] [1]) + m i n (c n t [2] [3], c n t [3] [2])$ 。

设第二种情况的数量为B，则

$B = (S - 2 A) \div 3$ 。

其中S为需要移动的数字的数量，

$S = c n t [1] [2] + c n t [1] [3] + c n t [2] [1] + c n t [2] [3] + c n t [3] [1] + c n t [3] [2]$ 。

答案为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;
}

# 三值的排序

# 分析

# 实现

三值的排序

分析

实现