C++ 高精度整数删除数字求最小值 - 贪心算法实现

C++ 高精度整数删除数字求最小值 - 贪心算法实现

问题描述： 给定一个高精度正整数'n' (n <= 1000 位)，需要删除其中任意's' 个数字，使得剩下的数字按原左右顺序组成一个新的正整数，要求找到一种方案，使得剩下的数字组成的数最小。

例如： '153748' 要删除 2 个数，使得剩下的数字最小，应当删除 '5' 和 '7'，得到 '1348'。

注意： '1087' 如果要删除 1 个数，删除 '1' 结果是最小的，得到结果 '87'。

输入：

第一行是一个高精度整数 'n' 第二行是需要删除的位数 's'

输出：

最后剩下的最小数

思路：

贪心算法：从高位到低位，每次删除当前位后面第一个比它小的数，如果找不到，则删除最后一位。

注意：

删除某个数需要把它后面的数往前移，所以可以先记录需要删除的数的位置，最后一起删除。

代码实现：

#include <iostream>
#include <vector>

using namespace std;

int main() {
    string n;
    int s;
    cin >> n >> s;

    vector<int> delete_pos;
    for (int i = 0; i < n.size() - 1; ++i) {
        for (int j = i + 1; j < n.size(); ++j) {
            if (n[j] < n[i]) {
                delete_pos.push_back(j);
                break;
            }
        }
    }

    // 删除最后 s 个数字
    if (delete_pos.size() < s) {
        delete_pos.resize(s, n.size() - 1);
    }

    // 从后往前删除
    for (int i = delete_pos.size() - 1; i >= 0; --i) {
        n.erase(n.begin() + delete_pos[i]);
    }

    cout << n << endl;

    return 0;
}