第四章上机实践报告

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），因为只遍历一遍。

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