自动搬运

查看原文

来自洛谷，原作者为

	yummy 这个人是时代的眼泪，什么也没有留下

搬运于2025-08-24 22:56:07，当前版本为作者最后更新于2024-02-24 12:09:04，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

A. String Minimization

本题涉及的主要知识点：

• 【2】字符串
• 【3】贪心法

题意分析

题目要在 $a$ 字典序尽量小的前提下求 $b$ 字典序最小值，所以先考虑 $a$ 什么时候字典序最小。

不难发现 $a$ 的两个不同位置之间没什么关系（$a_i$ 不管是否进行操作都不会产生 $a_j$，如果 $i\ne j$），所以我们只需要把每个字符都求出最小值即可。

总而言之：

• 若 $a_i<c_i$，则不能对 $i$ 操作。
• 若 $a_i>c_i$，则必须对 $i$ 操作。
• 若 $a_i=c_i$，则是否操作都可以。

接下来考虑最小化 $b_i$。若 $a_i\ne c_i$ 则是否操作已经确定，只有 $a_i=c_i$ 时，才会考虑“若 $b_i>d_i$ 则交换"。

总之，若 $a_i>c_i$，或者 $a_i=c_i$ 且 $b_i>d_i$，则必须交换 $b_i,d_i$。

参考程序

以下为 C++ 参考代码：

#include<bits/stdc++.h>
using namespace std;
int n;
string a,b,c,d;
int main(){
	cin>>n>>a>>b>>c>>d;
	for(int i=0;i<n;i++)
		if(a[i]>c[i] || a[i]==c[i] && b[i]>d[i])
			b[i]=d[i];
	cout<<b<<endl;
	return 0;
}

以下为 Python 3 参考代码。注意 Python 的字符串不能原地修改，必须转化成列表。

n=int(input())
a=input()
b=list(input())
c=input()
d=input()
for i in range(n):
    if a[i]>c[i] or a[i]==c[i] and b[i]>d[i]:
        b[i]=d[i]
print("".join(b))