自动搬运

查看原文

来自洛谷，原作者为

	leoljx 祝学习与生活全(bu)AC！

搬运于2025-08-24 21:58:30，当前版本为作者最后更新于2024-08-07 21:54:07，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

这是本人的第一篇题解，也是我第一道 AC 的蓝题！

说实在的，我认为这题不应该被评为蓝。

1. 最长公共前缀：考虑有两个字符串（以下简称串），它们的最长公共前缀就是它们前缀的最长部分 （有些偏废话了）。

2. 思路：三个串两两匹对，找到任意两个串的最长公共前缀，比较选出中最长的公共前缀（如样例中：一串与三串的最长公共前缀为 CAT ，这是三种两两匹配方案的串中最长的前缀，这就是我们的目标串），找到后只需计算将三个串都更新成目标串所用的步数即可（如样例中将三个串更新成 CAT 就是最少的步数）。

3. 特别的，如果查找后三种可能的公共前缀均为空（即三者两两匹配后没有公共前缀部分），那么把三串清空就是最少的步数。

4. 以下是 AC 代码（目前是全题解区中最简洁代码)：

#include<bits/stdc++.h>
using namespace std;
int nx,ny,nz,mxy,mxz,myz,maxn;
int n;
char x[100],y[100],z[100];//三个串
int main()
{
	cin>>nx>>x>>ny>>y>>nz>>z;
	while(x[mxy]==y[mxy]&&mxy<nx&&mxy<ny) mxy++;//mxy是指x串与y串的最长公共前缀的长度
	while(x[mxz]==z[mxz]&&mxz<nx&&mxz<nz) mxz++;//同理于上
	while(y[myz]==z[myz]&&myz<ny&&myz<nz) myz++;
	maxn=max(max(mxy,mxz),myz);//maxn是指最长的最长公共前缀的长度，即目标串的长度
	if(maxn==mxy) n=(nx-mxy)+(ny-mxy)+(nz-mxy)+(maxn-mxz)*2;
	else if(maxn==mxz) n=(nx-mxz)+(ny-mxz)+(nz-mxz)+(maxn-mxy)*2;
	else if(maxn==myz) n=(nx-myz)+(ny-myz)+(nz-myz)+(maxn-mxz)*2;//以上是计算更新成目标串所用的步数
	cout<<n;
    return 0;//good habit
}

通俗易懂，简约大方。希望大家能给蒟蒻一些鼓励，有不足之处请放宽直言。