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),因为只遍历一遍。

心得: 一开始的想法并不是这个,但是过于复杂,需要近百行代码,于是打算更换方法。复杂问题可以通过不同的方法进行简化,需要多加思考。

01-06 15:44