三值的排序

洛谷-P1459-三值的排序open in new window

分析

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

定义目标状态中的11...11区,22...22区,33...33区。

需要移动的第一种情况:xy区且yx区。操作数为1

需要移动的第二种情况:xy区,yz区,zx区。操作数为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;
}
最后修改于: