计蒜客 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)
还没有任何评论哟~
