1. 题目背景与核心需求解析
这道题目来自波兰信息学奥林匹克竞赛(POI)2019/2020赛季第一轮,编号P6661。题目名称"Pomniejszenie"在波兰语中意为"削减"或"减少",这直接揭示了题目的核心操作——通过对数字的特定修改来满足某种数学条件。
题目要求我们处理一个由数字组成的字符串(可以理解为超长整数),允许对其中的最多k位数字进行任意修改(可以增大或减小),目标是使得修改后的数字成为原数字所有可能修改结果中的最小值。这里的关键约束是:修改后的数字不能有前导零,且必须保持与原数字相同的位数。
举个例子,假设原数字是"1234",k=2。我们可以修改其中最多2位,比如把第2位'2'改成'1',第4位'4'改成'3',得到"1133"——这比原数字小,且是所有可能双位修改中最小的结果。
需要模型API调用? 免费领10W Token,多模型网关一键接入 Claude、DeepSeek 等主流模型。
2. 解题思路与算法设计
2.1 贪心算法的适用性分析
这类数字修改问题通常适合采用贪心算法,因为我们需要在每一步做出局部最优的选择,从而希望达到全局最优。具体到本题:
- 从左到右处理每一位数字(高位优先)
- 对于当前位,尝试将其改为尽可能小的数字
- 修改时要考虑剩余的可修改次数k
- 确保不会产生前导零(第一位不能改为0)
关键点在于:高位的修改对数值大小的影响远大于低位,因此应该优先处理高位数字。比如将"5123"的第一位'5'改为'4'(得到"4123")比修改后面任何三位对数值的减小效果都更显著。
2.2 具体实现步骤分解
- 输入处理:读取数字字符串和整数k
- 特殊情况处理:
- 如果数字长度为1,只能改为非零最小数字
- 如果k=0,直接返回原数字
- 主循环处理:
- 遍历数字的每一位(从高位开始)
- 对于当前位,尝试从0开始寻找可替换的最小数字
- 考虑剩余修改次数和首位非零限制
- 结果构造:记录每一步的修改,构建最终结果
2.3 边界条件与异常处理
- 前导零问题:第一位数字只能从1开始尝试修改
- 修改次数耗尽:当k减到0时立即停止修改
- 相同最小值选择:当有多种修改方式得到相同最小值时,选择修改次数最少的方案
- 大数处理:由于数字可能非常大(题目中长度可达1e5位),必须用字符串处理而非数值类型
3. C++实现详解
3.1 数据结构选择
使用std::string存储数字字符串,原因:
- 方便按索引访问每一位
- 长度不受限(相比数值类型)
- 修改单个字符效率高
cpp复制#include <iostream>
#include <string>
using namespace std;
3.2 核心算法实现
cpp复制string minimizeNumber(string num, int k) {
int n = num.size();
if (n == 1) {
// 处理单数字情况
num[0] = (k >= 1) ? '1' : num[0];
return num;
