自动搬运

查看原文

来自洛谷，原作者为

	Vix AFO

搬运于2025-08-24 22:35:25，当前版本为作者最后更新于2022-09-24 15:47:48，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

原题链接

题意

给定只包含 $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指出。