题解 | #小O的五号倍数#

题目链接

小O的五号倍数

题目描述

给定一个正整数 $x$ （以字符串形式），你需要删除其中的若干个数位，使得留下的数位按原顺序组成的新数字是 5 的倍数。目标是最小化删除的数位数。注意，可以将所有数位都删除，此时数字视为 0。

解题思路

最小化删除数位的数量，等价于最大化保留数位的数量。

1. 核心条件

一个整数是 5 的倍数，其充要条件是它的个位数字（最后一位）是 0 或 5。

2. 问题转化

因此，我们的任务是在原始数字字符串中，寻找一个子序列，它构成的数字是 5 的倍数，并且这个子序列的长度要尽可能长。

一个子序列构成的数字要成为 5 的倍数，必须满足：

它的最后一位是 '0' 或 '5'。
它不能有前导零，除非这个数字本身就是 "0"。

3. 关键洞察：子序列 vs 子串

假设我们找到了一个满足条件的、由子序列构成的最长数字。它的第一个数字来自原串的索引 $i$ ，最后一个数字来自原串的索引 $j$ （ $i \le j$ ）。为了最大化长度，我们是否应该保留所有在原串中位于 $i$ 和 $j$ 之间的数字呢？答案是肯定的。因为保留这些中间的数字不会改变最后一位（决定是否为5的倍数），也不会制造出前导零（因为第一位已经是非零），只会让最终的数字更长。

这个洞察告诉我们，我们要寻找的最长合法子序列，实际上就是最长的合法子串。

4. 算法流程

现在问题简化为寻找满足条件的最长子串。一个合法的子串必须以 '0' 或 '5' 结尾，并且不能以 '0' 开头（特殊情况 "0" 除外）。

我们可以分两种情况来确定可以保留的最大长度 max_len：

情况一：最终构成的数字是 "0"

题目允许我们将所有数位删除，得到数字 0，它是 5 的倍数。这个方案总是可行的。如果原始字符串中包含至少一个 '0'，我们就可以通过只保留这一个 '0' 来实现，此时保留的长度为 1。这是我们计算 max_len 的一个基础值。
情况二：最终构成的数字非零

一个非零的合法子串必须以非零数字开头，并以 '0' 或 '5' 结尾。为了让这个子串最长，我们应该：
1. 找到原字符串中第一个非零数字的位置，作为子串的起始点。设其索引为 first_nonzero_idx。
2. 从这个起始点开始，向后遍历字符串。
3. 当我们遍历到索引 i 时，如果 x[i] 是 '0' 或 '5'，我们就找到了一个合法的候选子串，即从 first_nonzero_idx 到 i 的部分。其长度为 i - first_nonzero_idx + 1。
4. 我们只需在所有这些候选子串中，找到最长的那一个。

整合步骤：

初始化最大保留长度 max_len = 0。
检查原字符串 $x$ 中是否存在 '0'。如果存在，说明我们至少可以构成数字 "0"，因此将 max_len 初始化为 1。
找到字符串 $x$ 中第一个非零数字的索引 first_nonzero_idx。
如果找不到非零数字（即 $x$ 是 "0"、"00" 等），那么 max_len 就是 1，直接进入最后一步。
否则，从 first_nonzero_idx 开始遍历到字符串末尾。对于每个索引 i：
- 如果 x[i] 是 '0' 或 '5'，计算当前子串长度 len = i - first_nonzero_idx + 1。
- 更新 max_len = max(max_len, len)。
最终，max_len 就是我们能保留的最大位数。最少需要删除的位数即为 x.length() - max_len。

代码

cpp
java
python

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

void solve() {
    string x;
    cin >> x;

    int n = x.length();
    int max_len = 0;

    if (x.find('0') != string::npos) {
        max_len = 1;
    }

    int first_nonzero_idx = -1;
    for (int i = 0; i < n; ++i) {
        if (x[i] != '0') {
            first_nonzero_idx = i;
            break;
        }
    }

    if (first_nonzero_idx != -1) {
        for (int i = first_nonzero_idx; i < n; ++i) {
            if (x[i] == '0' || x[i] == '5') {
                int current_len = i - first_nonzero_idx + 1;
                max_len = max(max_len, current_len);
            }
        }
    }

    cout << n - max_len << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            String x = sc.next();
            solve(x);
        }
    }

    private static void solve(String x) {
        int n = x.length();
        int maxLen = 0;

        if (x.contains("0")) {
            maxLen = 1;
        }

        int firstNonZeroIdx = -1;
        for (int i = 0; i < n; i++) {
            if (x.charAt(i) != '0') {
                firstNonZeroIdx = i;
                break;
            }
        }

        if (firstNonZeroIdx != -1) {
            for (int i = firstNonZeroIdx; i < n; i++) {
                char c = x.charAt(i);
                if (c == '0' || c == '5') {
                    int currentLen = i - firstNonZeroIdx + 1;
                    maxLen = Math.max(maxLen, currentLen);
                }
            }
        }

        System.out.println(n - maxLen);
    }
}

import sys

def solve():
    x = sys.stdin.readline().strip()
    n = len(x)
    max_len = 0

    if '0' in x:
        max_len = 1

    first_nonzero_idx = -1
    for i, char in enumerate(x):
        if char != '0':
            first_nonzero_idx = i
            break
    
    if first_nonzero_idx != -1:
        for i in range(first_nonzero_idx, n):
            if x[i] == '0' or x[i] == '5':
                current_len = i - first_nonzero_idx + 1
                max_len = max(max_len, current_len)

    print(n - max_len)


def main():
    t = int(sys.stdin.readline())
    for _ in range(t):
        solve()

if __name__ == "__main__":
    main()

算法及复杂度

算法: 贪心、字符串处理
时间复杂度: 算法主要包括几次对字符串的线性扫描（查找'0'、查找第一个非零数字、主循环）。每次扫描的时间复杂度都是 $\mathcal{O}(N)$ ，其中 $N$ 是数字字符串的长度。因此，每个测试用例的总时间复杂度为 $\mathcal{O}(N)$ 。
空间复杂度: 算法仅使用了常数个额外变量和存储输入的字符串，因此空间复杂度为 $\mathcal{O}(N)$ 。