首页 > 试题广场 >

小红的字符串

[编程题]小红的字符串
  • 热度指数：2357 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\hspace{15pt}小红拥有一个长度为 n 的小写字母字符串 s。她可以重复执行如下操作任意次：
\hspace{23pt}\bullet\, 选择一个下标 i\ (1\leqq i\leqq n)，将字符 s_i 循环右移到字母表中的下一个字母。特别地，``\texttt{z}`` 右移后变成 ``\texttt{a}``。
\hspace{15pt}
\hspace{15pt}请计算，使 s 变为回文串所需的最少操作次数。

\hspace{15pt}【名词解释】回文串：一个字符串从左往右与从右往左读完全相同。

输入描述:
\hspace{15pt}一行输入一个长度不超过 1000 的小写字母字符串 s。


输出描述:
\,\,\,\,\,\,\,\,\,\,在一行上输出一个整数，代表把 s 变成回文串的最少操作次数。
示例1

输入

abcd

输出

4

说明

一种可行方案：\texttt{（共 4 次操作）。
示例2

输入

nuhhhh

输出

19
算法知识视频讲解
添加回答
C
人生有三乐头像 人生有三乐
#include <stdio.h>
#include <string.h>

int main() {
    //没刷过题真不懂用贪心算法。循环右移原来指的是单个字母+1变成下一个字母不是位置移动
    //贪心的过程就是判断左边移动多点还是右边移动多点，贪最少的那一边就行，看来不难
    int a, b;
    char string[1000];
    scanf("%s",string);
    int l=strlen(string);
    //printf("%c",string[l-1]);

    int buzhou=0;//统计要走多少步
    for(int i=0;i<l-1-i;i++)
    {
        int j=l-1-i;  //尾部的字母
        //比较两边哪边花的步数少
        if(string[i]<string[j])
        {
            int temp1=string[j]-string[i]; //正常右移的步数
            int temp2='z'-string[j]+(string[i]-'a')+1;   //大的那个右移是否更小

            //选更小的加,贪心
            if(temp1<temp2)
            {
                buzhou+=temp1;
            }else {
                buzhou+=temp2;
            }
        }else if(string[i]>string[j]){
            int temp1=string[i]-string[j]; //正常右移的步数
            int temp2='z'-string[i]+(string[j]-'a')+1;   //大的那个右移是否更小

            //选更小的加,贪心
            if(temp1<temp2)
            {
                buzhou+=temp1;
            }else {
                buzhou+=temp2;
            }
        }else {  //相等就不管
            continue;
        }
    }

    printf("%d",buzhou);
   
    return 0;
}
发表于 2025-10-03 11:50:54 回复(0)
提交观点

问题信息

贪心
难度：
1条回答 213浏览

热门推荐

相关试题

小红的字符串

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号