题干大意
把一个长度为n的英文小写字符串变为回文串,初始指针下标为p,指针可左右移动改变下标,向上下移动改变字母,比如a向上移动一次变为b,每移动一位下标或者字母变化一次操作次数+1,字母变化和指针下标移动都遵守循环,即下标在最后一个字母位置再往右移则回到第一个字母位置,a向下移一次则变为z。求最少操作次数。
分析
贪心题,对于循环条件其实只有字母变化有用处,下标循环变化完全没用。直接把字符串一分为二,因为回文左右是对称的,所以只操作一边即可。
之后的关键点在于两个,首先是每个不同字母变化最小操作次数,这个很好解决,直接min(abs(a[i]-a[n+1-i]),26-abs(a[i]-a[n+1-i]))即可。其次是指针下标该怎么移,指针若是在所有要变化字母的左边,则直接往右扫,同理在右边则往左扫,若是在中间某位置,则要判断先左再右和先右再左哪个操作次数更少,为此则需要记下第一个和最后一个要变化的字母下标位置,这样就好判断左右先后问题了。
题解
#include"bits/stdc++.h"
using namespace std;
const int M = 1e5+7;
char str[M];
int main(){
int n,p;
cin>>n>>p;
cin>>str+1;
int sumchg=0;
int first=-1;
int last=-1;
int differ;
for(int i=1;i<=n/2;++i){
differ=abs(str[i]-str[n+1-i]);
if(differ!=0){
if(first<0) first=i;
last=i;
sumchg+=min(differ,26-differ);
}
}
if(sumchg==0){
cout<<0;
}
else{
if(p>n/2) p=n+1-p;
int ans=0;
if(p<=first) ans+=sumchg+last-p;
else if(p>=last) ans+=sumchg+p-first;
else ans+=min(2*(p-first)+last-p,2*(last-p)+p-first)+sumchg;
cout<<ans;
}
return 0;
}