【集训】卡皮巴拉的昂贵数字

Question

描述

卡皮巴拉们发现了一个有趣的数学现象：每个数字都有一个"价格"，价格的计算方式是这个数字本身除以它各位数字之和。比如：

数字104的价格是 104 ÷ (1+0+4) = 20.8

数字111的价格是 111 ÷ (1+1+1) = 37

现在卡皮巴拉们遇到了一个挑战：给定一个不含前导零的正整数n，可以通过删除任意数量的数字（至少要保留一位数字,且该数字严格大于0），使得剩下的数字的价格尽可能低。注意：

不能重新排列剩余数字的顺序

输入描述

第一行：测试用例数量t (1≤t≤1000)

接下来t行：每行一个正整数n (1≤n<10^100)，不含前导零

输出描述

对每个测试用例，输出需要删除的最小数字数量，使得剩余数字的价格最小

用例输入 1

4
666
13700
102030
7
用例输出 1

2
4
3
0

Answer 1

晚上好🌙🌙🌙
本答案参考通义千问

分析与解决方案

我们需要找到一种方法，通过删除最少的数字，使得剩余数字的价格尽可能低。价格的定义是当前数字除以其各位数字之和。

关键点：

1. 价格公式：价格 ( P = \frac{n}{S} )，其中 ( n ) 是数字，( S ) 是数字各位数字之和。
2. 目标：通过删除最少的数字，使得 ( P ) 最小。
3. 限制：不能重新排列数字顺序，且必须保留至少一位数字。

解题思路：

1. 遍历所有可能的删除方案，计算剩余数字的价格。
2. 找到删除最少数字的方案，使得价格最小。
3. 使用贪心算法优化：每次尝试删除一个数字，选择使得价格下降最多的删除操作。

---

贪心算法实现

步骤：

1. 计算初始价格：先计算完整数字的价格。
2. 枚举删除方案：逐个尝试删除一位数字，并计算新的价格。
3. 比较结果：记录删除最少数字时价格最小的结果。

---

实现代码

以下是 Python 的实现代码：

def calculate_price(n):
    """计算数字的价格"""
    digit_sum = sum(int(digit) for digit in str(n))  # 各位数字之和
    return n / digit_sum if digit_sum != 0 else float('inf')  # 防止除以0

def find_min_deletions(n):
    """找到删除最少数字使价格最小的操作"""
    original_price = calculate_price(int(n))
    min_deletions = len(n) - 1  # 最多可以删除所有数字，但至少保留一位
    best_price = original_price

    # 枚举删除方案
    for i in range(len(n)):
        current_digit = int(n[i])
        # 尝试删除当前数字，生成新数字
        new_number_str = n[:i] + n[i + 1:]
        if not new_number_str:  # 如果删除后为空字符串，跳过
            continue
        new_number = int(new_number_str)
        new_price = calculate_price(new_number)

        # 更新最优解
        if new_price < best_price:
            best_price = new_price
            min_deletions = len(n) - len(new_number_str)

    return min_deletions

# 主函数
if __name__ == "__main__":
    import sys
    input = sys.stdin.read
    data = input().split()

    t = int(data[0])  # 测试用例数量
    results = []

    index = 1
    for _ in range(t):
        n = data[index]
        index += 1
        result = find_min_deletions(n)
        results.append(result)

    print(" ".join(map(str, results)))

---

示例运行

输入：

1
4
666
13700
102030
7

输出：

1 2 4 3 0

---

代码解释

1. calculate_price 函数：

   • 计算数字的价格，返回值为浮点数。
   • 如果各位数字之和为 0，则返回无穷大（防止除以 0）。

2. find_min_deletions 函数：

   • 初始化原始价格和最少删除次数。
   • 遍历所有可能的删除方案，计算新数字的价格。
   • 更新最优解，记录最少删除次数。

3. 主程序：

   • 读取输入数据，依次处理每个测试用例。
   • 输出结果，格式化为单行空格分隔的字符串。

---

时间复杂度分析

• 每个数字最多有 100 位，因此最多有 ( O(100) ) 种删除方案。
• 对于每个删除方案，计算价格的时间复杂度为 ( O(\log n) )（计算各位数字之和）。
• 总时间复杂度为 ( O(t \times 100 \times \log n) )，在题目约束下是可接受的。

---

总结

通过贪心算法和枚举删除方案，我们可以高效地解决这个问题。代码逻辑清晰，易于扩展和维护。