4-2 删数问题 (110 分)
给定n位正整数a,去掉其中任意k≤n 个数字后,剩下的数字按原次序排列组成一个新 的正整数。对于给定的n位正整数a和正整数 k,设计一个算法找出剩下数字组成的新数最 小的删数方案。
输入格式:
第 1 行是1 个正整数 a。第 2 行是正整数k。
输出格式:
输出最小数。
输入样例:
在这里给出一组输入。例如:
178543
4
输出样例:
在这里给出相应的输出。例如:
13
#include<iostream> #include<string> using namespace std; int main() { string a; int k, n; cin >> a >> k; n = a.size(); while (k--) { for (int i = 0;i < n;i++) { if (a[i] > a[i + 1] || i == n - 1) { a.erase(i, 1); break; } } n = a.size(); } while (a[0] == '0') a.erase(0, 1); cout << a; system("pause"); }
贪心策略: 前后两个数比较,若前数大于后数,则删除前数;若后数大于前数,则不变。
直到最后,若是没有删除足够的数,则从后面开始删除。
算法复杂度: O(n),因为只遍历一遍。
心得: 一开始的想法并不是这个,但是过于复杂,需要近百行代码,于是打算更换方法。复杂问题可以通过不同的方法进行简化,需要多加思考。