Advertisement

计蒜客 T1279 型号的最小距离字符串

阅读量:

定义两个等长字符串 A 与 B 的距离 dis(A,B) 为:在相同位置上字符不同的数量。

给定三个长度均为 n 的小写字母字符串 A、B、C,要求构造一个长度为 n 的字符串 S,使得 dis(S,A) + dis(S,B) + dis(S,C) 的值达到最小。为了简化问题,只需输出该最小值即可。

输入格式
输入包含三行,每行对应一个字符串,分别为 A、B、C。这些字符串均为非空的小写字母构成,并且长度一致。
所给字符串的长度不会超过 2×105。

输出格式
输出最小的 dis(S,A) + dis(S,B) + dis(S,C) 的值。

样例解释
当 S 为 "turtle" 时取得最优解。

输出时每行末尾存在的多余空格不会对答案的正确性造成影响。

样例输入
needle
turkey
bottle
样例输出
10

对于这道贪心算法的问题,目前尚不清楚具体解法,做法是参考了他人的思路<>>

复制代码
    #include<iostream>
    using namespace std;
    #include <cstring> 
    #include <cstdio>
    #include <set>
    
    const int maxn=200000+5;
    ch

全部评论 (0)

还没有任何评论哟~