1. Job Roadmap
  2. Home
  3. Problem Set
  4. codenotelist
  5. Forum
  6. course
  7. Shore Share Sessions
  8. Record
  1. Login
  2. Sign Up
  3. Language
    1. English
    2. 한국어
    3. 简体中文
    4. 正體中文
    ZhContent TextSol AI分析

解题思路

  • 将 26 个小写字母看作首尾相接的环(a 与 z 相邻)。一次操作可把某个字母改成其相邻字母。
  • 若把所有字符都改成同一个目标字母 t,把字符 c 改到 t 的最小代价为环形距离 dist(c,t) = min(|pos(c)-pos(t)|, 26 - |pos(c)-pos(t)|),其中 pos(x)=ord(x)-ord('a')。
  • 对每个目标字母 t ∈ [0..25] 累加整串的代价,取最小值即答案。
  • 相关算法:枚举 + 环形距离(最短路等价为贪心选最近方向)。因为目标字母只有 26 个,复杂度近似线性。

复杂度分析

P4251.第2题-游游的字母串

    1000ms Tried: 47 Accepted: 23 Difficulty: 3 所属公司 : 中国移动
    算法与标签>暴力枚举

题目内容

对于一个小写字母而言,游游可以通过一次操作把这个字母变成相邻的字母。'aaa' 和 'bbb' 相邻,'bbb' 和 'ccc' 相邻,以此类推。特殊的,'aaa' 和 'zzz' 也是相邻的。可以认为,小写字母的相邻规则为一个环。

游游拿到了一个仅包含小写字母的字符串,她想知道,使得所有字母都相等至少要多少次操作?

输入描述

一个仅包含小写字母,长度不超过 100000100000100000 的字符串。

输出描述

一个整数,代表最小的操作次数。

样例1

输入

yab

输出

3

说明

第一次操作,把 'yyy' 变成 'zzz' ,字符串变成了 "zabzabzab"

第二次操作,把 'bbb' 变成 'aaa' ,字符串变成了 "zaazaazaa”

第三次操作,把 'zzz' 变成 'aaa' ,字符串变成了 "aaaaaaaaa"

登录后即可使用 AI 分析。

模式
倒计时时长
:

最长 10 小时 59 分;应用后按此时长重新开始。

提示:点击提交记录在左侧题面区域查看详情
题库
AI分析设置
留空使用官方API Key,每天有次数限制(自定义API Key仅限会员和管理员使用,不限次数)
会员和管理员可切换模型;切到 Kimi/智谱/通义/豆包时需填写对应供应商 API Key
升级会员,可将运行与提交冷却时间缩短至 1 秒起

Status

  • Judging Queue
  • Service Status

Development

  • Open Source

Support

  • Help
  • Contact Us

About

  • About
  • Privacy
  • Terms of Service
  • Copyright Complaint
  1. Language
    1. English
    2. 한국어
    3. 简体中文
    4. 正體中文
  2. Legacy mode
  3. Theme
    1. Light
    2. Dark
  1. 京ICP备2025123107号-1
  2. Worker 3, 34ms
  3. Powered by Hydro v5.0.0-beta.18 Community
CLOSE


ScanQRCodePrompt

请使用微信扫描下方二维码完成注册

Forgot password or username?