📝 题目大意

有一个收银机，初始显示为 $0$。有 $11$ 个按钮：00（将当前数字乘 $100$）和 0 ~ 9（将当前数字乘 $10$ 再加该数字）。给定目标整数 $S$（以字符串形式给出，长度可达 $10^5$），求最少按键次数。

💡 解题思路

1. 题目分析：

   • $S$ 的长度上限为 $10^5$，远超过 $64$ 位整数范围，必须用字符串处理。
   • 每次按键本质上是在当前数字的末尾拼接若干位：按 0~9 拼接 $1$ 位，按 00 拼接 $2$ 位（两个 $0$）。
   • 因此问题转化为：给定字符串 $S$，每次可以消耗 $1$ 次操作输出 $1$ 个字符，或者消耗 $1$ 次操作输出连续的两个 0（即 00 按钮），求最少操作次数。

2. 算法推导：

   • 设 $S$ 的长度为 $n$（对应代码中的 n），答案初始为 $0$（对应代码中的 ans）。
   • 从左到右扫描 $S$（下标 $i$ 从 $0$ 到 $n-1$）：
     • 若当前字符 s[i] 和下一个字符 s[i+1] 均为 '0'，则可以使用一次 00 按钮同时处理这两个字符：i++ 跳过下一个字符，ans++。
     • 否则，当前字符只能单独用一个按钮处理：ans++。
   • 贪心正确性：遇到连续两个 0 时使用 00 按钮，比分别用两次 0 按钮节省 $1$ 次操作，且不会影响后续字符的匹配（因为 00 按钮恰好消耗相邻的两个 0），不存在"拆开更优"的情况。

3. 边界与细节：

   • 当 $i = n-1$（最后一个字符）时，s[i+1] 为字符串结束符 '\0'，不等于 '0'，自动走 else 分支，不会越界。
   • 注意 i++ 在 if 体内执行后，for 循环的 i++ 还会再执行一次，因此总共跳过了两个字符，逻辑正确。

⏱️ 复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 为字符串 $S$ 的长度，仅需一次线性扫描。
• 空间复杂度：$O(n)$，用于存储输入字符串 $S$。

💻 标准代码 (C++)

#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s; cin >> s;          // 以字符串读入 S（因为可能超出 64 位整数范围）
    int n = s.size(), ans = 0;   // n: 字符串长度, ans: 最少按键次数
    for(int i = 0; i < n; i++)
    {
        // 若当前和下一个字符都是 '0'，可以用一次 "00" 按钮处理两个字符
        if(s[i] == '0' && s[i + 1] == '0') i++;  // 跳过下一个字符
        ans++;  // 无论用 "00" 还是单个数字按钮，都消耗 1 次操作
    }
    cout << ans;
    return 0;
}