C++ 实现：从大整数中删数求最小密码的巧妙算法

# C++实现：删除数字使剩余数最小 以下是解决这个问题的C++实现代码，使用贪心算法思想： ```cpp #include <iostream> #include <string> #include <vector> using namespace std; string findMinNumber(string num, int s) { vector<char> stack; for (char digit : num) { while (!stack.empty() && s > 0 && stack.back() > digit) { stack.pop_back(); s--; } stack.push_back(digit); } // 如果还需要删除更多数字，从末尾删除 while (s > 0 && !stack.empty()) { stack.pop_back(); s--; } // 构建结果字符串 string result; for (char digit : stack) { result += digit; } // 去除前导零 size_t nonZero = result.find_first_not_of('0'); if (nonZero != string::npos) { result = result.substr(nonZero); } else { result = "0"; // 全为零的情况 } return result.empty() ? "0" : result; } int main() { string N; int S; cin >> N >> S; string password = findMinNumber(N, S); cout << password << endl; return 0; } ``` ## 代码说明 1. 使用贪心算法思想，维护一个栈结构 2. 遍历数字字符串，当栈顶数字大于当前数字时弹出栈顶(这样可以确保剩余数字最小) 3. 处理完所有数字后，如果还需要删除更多数字，从末尾删除 4. 最后去除结果中的前导零 ## 测试用例验证 样例输入1: ``` 2813465 4 ``` 输出: ``` 134 ``` (删除2,8,6,5) 样例输入2: ``` 1032 2 ``` 输出: ``` 2 ``` (删除1和0) ## 注意事项 1. 算法时间复杂度为O(n)，n为输入数字的位数 2. 需要特别注意前导零的处理 3. 当删除所有数字后剩余零的情况需要特殊处理 ######[AI写代码神器 | 473点数解答 | 2025-06-20 16:08:21]