题解

题目分析

本题要求通过两种操作将任意大整数 $n$ 变为 $1$，求最少操作次数：

1. 加1操作：数字增加 1
2. 循环右移操作：将最高位移到最低位，并去除前导零

核心思路

主要观察

• 目标数字 $1$ 只有一位，因此最终需要通过循环右移操作得到单数字 1
• 循环右移操作实际上是在所有循环移位中寻找最优路径
• 数字全为 9 时是特殊情况，需要额外处理

算法策略

1. 贪心预处理：对于当前数字，先通过加1操作将最后一位变为 9
2. 循环移位：然后进行循环右移，重复上述过程
3. 边界处理：当数字全为 9 时，直接通过两次操作变为 1（加1→全0→循环移位→1）
4. 局部优化：尝试对最后几位进行不同的加1策略，寻找更优解

算法步骤

主函数 solve(string s)

1. 初始化：将数字存入双端队列，统计 9 的个数
2. 循环处理：
   • 去除前导零
   • 如果已经是 "1"，返回当前操作数
   • 如果最后一位不是 0，通过加1操作将其变为 9
   • 执行循环右移操作
3. 全9处理：当数字全为 9 时，额外增加 2 次操作

主程序优化

• 对最后 1-8 位尝试不同的加1方案
• 计算每种方案的总操作数，取最小值

关键技巧

1. 九的利用：将数字末尾变为 9，便于后续通过循环移位获得更小的数字
2. 双端队列：高效处理循环移位操作
3. 局部搜索：对末尾几位枚举不同加1策略，避免陷入局部最优

算法标签

• 贪心算法 (Greedy Algorithm)
• 广度优先搜索 (BFS) 的思想
• 字符串处理 (String Manipulation)
• 大数运算 (Big Integer Arithmetic)

复杂度分析

• 时间复杂度：$O(k \cdot L)$，其中 $L$ 是数字长度，$k$ 是尝试的局部方案数（最多8）
• 空间复杂度：$O(L)$，存储数字的各位

样例验证

样例 1: 301

• 算法过程：301→309→93→100→1
• 操作数：8+1+7+1=17 ✓

样例 2: 1000000

• 直接循环右移得到 1
• 操作数：1 ✓

该算法通过贪心策略结合局部搜索，高效解决了大数情况下的最优操作问题。