【洛谷贪心算法】P1106删数问题
这道题可以使用贪心算法来解决，核心思路是尽量让高位的数字尽可能小。当我们逐步删除数字时，会优先删除高位中相对较大的数字。具体做法是从左到右遍历数字序列，当发现当前数字比它后面的数字大时，就删除当前数字，直到删除了S个数字或者遍历完整个序列。如果遍历完后删除的数字个数还不够S个，就从序列的末尾继续删除。
【算法思路】
- 输入处理：使用
string类型存储高精度的正整数num，并读取要删除的数字个数s。
这道题为什么用字符串存储而不是数组存储？
①处理大整数的便利性：题目中明确提到输入的是一个高精度的正整数，且不超过 250 位。普通的整数类型（如 int、long long）所能表示的数值范围是有限的，无法存储如此大的数字。字符串可以轻松地存储任意长度的数字序列，它本质上是字符数组，每个字符对应数字的一位，不受数值范围的限制。例如，对于一个 200 位的大整数，使用字符串可以直接将其按位存储，不会出现溢出问题。
②操作的灵活性：在本题中，需要进行删除数字的操作。字符串提供了方便的方法来删除指定位置的字符，例如在 C++ 中可以使用 erase 函数。对于字符串 str，可以使用 str.erase(i, 1) 轻松删除第 i 个位置的字符。
//数组存储
vector<int> num(n);
int k;
for(int i=0;i<n;i++){
cin>>num[i];
}
cin>>k;
//字符串存储
string num;
int k;
cin>>num>>k;
- 删数操作
- 进入一个循环，循环次数为
k次。 - 在每次循环中，从左到右遍历
num，找到第一个满足num[i] > num[i + 1]的位置i，然后删除该位置的数字。 - 如果内层循环结束后
deleted仍然为false，说明在当前数字字符串中没有找到递减的位置，此时使用num.erase(num.length() - 1, 1)删除字符串的最后一个字符，并将k减 1。
-
去除前导零：删数操作完成后，可能会出现前导零的情况，因此需要去除前导零。
- 定义int类型的变量start变量初始化为0，用于记录数字字符串中第一个非零字符的位置。
- 进入
while (start < num.length() && num[start] == '0')循环，从字符串的开头开始遍历，只要没有遍历到字符串末尾且当前字符是0，就将start加1。 - 用三目运算符处理前导零并且给num赋予合适的值。
-
输出结果：如果去除前导零后
num为空，说明最终结果为 0，输出0；否则输出num。
【代码示例】
#include<iostream>
#include<string>
using namespace std;
int main(){
string num;
int k;
cin>>num>>k;
//进行k次删除操作
while(k > 0){
bool deleted=false;//标记是否找到递减位置
for(int i=0;i < num.length()-1;++i){
if(num[i] > num[i+1]){
//找到第一个递减的位置，删除改位置的数字
num.erase(i,1);
deleted=true;
k--;
break;
}
}
//如果没找到递减位置，删除末尾字符
if(!deleted){
num.erase(num.length() - 1,1);
k--;
}
}
//去除前导零
int start=0;
while (start < num.length() && num[start] == '0'){
start++;
}
num = (start==num.length()) ? "0" : num.substr(start);
cout<<num<<endl;
return 0;
}
注意：
-
边界处理：若序列完全递增，删除末尾数字
-
substr：是 std::string 类的一个成员函数，num.substr(start) 会返回从字符串 num 的第 start 个位置开始一直到字符串末尾的子字符串。