题解：P16865 [GKS 2021 #H] Transform the String

SCX2014 · 2026-06-11 14:53:10 · 题解

题目大意

给你两个字符串 S 和 F，你需要对字符串 S 进行若干次操作，使字符串 S 中的每个字母都出现在字符串 F 中。

每次操作可以将字符串中的一个字母改为字母表中它的前一个或后一个字母，且字母表被视为循环的，即字母 a 的前一个字母是 z，字母 z 的后一个字母是 a。

问最少需要进行几次操作才能达到目标。

算法分析

对于字符串 S 的每一位，其若干次变化后的字符一定是在字符串 F 的所有字符中离自己最近的，而这个变化次数只要知道了变化后的字符就很好求了。

注意到数据范围 1≤|F|≤26，而且 F 仅由互不相同的小写英文字母组成，那么考虑枚举 F 的每一位，更新每个小写英文字母的最小变化次数，最后枚举 S 的每一位，累和就行了。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int mp[305];
int main(){
   std::ios::sync_with_stdio(0);
   cin.tie(0),cout.tie(0);
   int T,id=0;
   cin>>T;
   while(T--){
      cout<<"Case #"<<++id<<": ";
      for(char i='a';i<='z';i++){
         mp[i]=0x3f;//初始值设为无限大
      }
      string s,f;
      cin>>s>>f;
      int n=s.size();
      s=" "+s;
      for(int i=0;i<f.size();i++){//枚举每一位
         for(char j='a';j<='z';j++){//枚举每个字母
            mp[j]=min(mp[j],min(abs(j-f[i]),26-abs(j-f[i])));//更新最小变化次数
         }
      }
      int ans=0;
      for(int i=1;i<=n;i++){
         ans+=mp[s[i]];//累和
      }
      cout<<ans<<'\n';
   }
   return 0;
}