当前位置: 代码迷 >> 综合 >> Code Forces 486C Palindrome Transformation
  详细解决方案

Code Forces 486C Palindrome Transformation

热度:51   发布时间:2023-12-12 23:17:28.0

题干大意

把一个长度为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;
}
 

  相关解决方案