P8040 [COCI2016-2017#7] IGRA 题解

· · 题解

原题链接

题意

给定只包含 a ,b, c 三种字母的两个长度相等的字符串 S, T, 只改变 S 串字母位置后得到的新串 S'，使得 \forall i \in [1,|T|], 都满足 {S'}_ i \ne T_i，求字典序最小的 S'。

范围：|S |= |T|, 1 \le |S| \le 5000。

分析

首先有且仅有 a,b,c 三个字母，又要满足字典序最小，容易想到贪心，因为对于 T 串中的每一个字母，我们最多只有两个字母可以选择。比如当 T_i = a 时，那么 S'_ i = b 或 c。现在问题就转化成了在两个字母中选择哪一个，贪心地想，显然选择字典序更小的字母更优，但是原题限制了S' 是由 S 变幻而来的，所以 S 串中 a,b,c 的数量是一定的，可能当前选了某个字母后，剩下的字母无法让 S' 和 T 每一位都不等。所以正确的策略应该是在保证 S' 和 T 每一位都不等的情况下，选择更优的字母。

怎样保证不等呢？记 S 中剩余的 a,b,c 的数量为 cnt_a, cnt_b, cnt_c，T 中剩余的 a,b,c 的数量为 aim_a, aim_b, aim_c，恒有 cnt_a + cnt_b \ge aim_c, cnt_a + cnt_c \ge aim_b, cnt_b + cnt_c \ge aim_a。假如要选择 a，就要满足 cnt_a - 1 + cnt_b \ge aim_c 并且 cnt_a - 1 + cnt_c \ge aim_b，b,c 以此类推，因为只有三个字母，可以直接判断，时间复杂度 O(|S|)。

Code

#include <bits/stdc++.h>
using namespace std;

const int N = 5e3 + 10;
int n;
char s[N];
int cnt[3], aim[3];
//用 0, 1, 2 代表 a, b, c

int main() {
    scanf("%d%s", &n, s + 1);
    for (int i = 1; i <= n; i++)
        if (s[i] == 'a') cnt[0]++;
        else if (s[i] == 'b') cnt[1]++;
        else cnt[2]++;

    scanf("%s", s + 1);
    for (int i = 1; i <= n; i++)
        if (s[i] == 'a') aim[0]++;
        else if (s[i] == 'b') aim[1]++;
        else aim[2]++;

    for (int i = 1; i <= n; i++)
        if (s[i] == 'a') {
            aim[0]--;
            if (cnt[1] && cnt[1] - 1 + cnt[2] >= aim[0] && cnt[1] - 1 + cnt[0] >= aim[2]) cnt[1]--, printf("b");
            else cnt[2]--, printf("c");
        } else if (s[i] == 'b') {
            aim[1]--;
            if (cnt[0] && cnt[0] - 1 + cnt[1] >= aim[2] && cnt[0] - 1 + cnt[2] >= aim[1]) cnt[0]--, printf("a");
            else cnt[2]--, printf("c");
        } else {
            aim[2]--;
            if (cnt[0] && cnt[0] - 1 + cnt[1] >= aim[2] && cnt[0] - 1 + cnt[2] >= aim[1]) cnt[0]--, printf("a");
            else cnt[1]--, printf("b");
        }
    return 0;
}

后话

建议评橙，考场上很快就想到正解了，不是很难的贪心，听机房的人说可以用爆搜过，tql

这是本蒟蒻的第一篇题解，有什么错还请dalao指出。