c++ - 给定数字 N 消除 K 数字以获得最大可能数字

Question

正如标题所说，任务是:

给定号码N消除 K数字以获得最大可能的数字。数字必须保持原位。

示例:n = 12345 , k = 3 , max = 45 (前三位数字被删除，数字不得移动到另一个位置)。

知道如何解决这个问题吗？
(不是作业，我是准备算法大赛，在线评委上解题。)

1 <= N <= 2^60 , 1 <= K <= 20 .

编辑:这是我的解决方案。它正在工作:)

#include <iostream>
#include <string>
#include <queue>
#include <vector>
#include <iomanip>
#include <algorithm>
#include <cmath>

using namespace std;


int main()
{
    string n;
    int k;

    cin >> n >> k;

    int b = n.size() - k - 1;
    int c = n.size() - b;
    int ind = 0;
    vector<char> res;
    char max = n.at(0);

    for (int i=0; i<n.size() && res.size() < n.size()-k; i++) {
        max = n.at(i);
        ind = i;
        for (int j=i; j<i+c; j++) {
            if (n.at(j) > max) {
                max = n.at(j);
                ind = j;
            }
        }

        b--;
        c = n.size() - 1 - ind - b;
        res.push_back(max);
        i = ind;
    }

for (int i=0; i<res.size(); i++)
    cout << res.at(i);

cout << endl;

    return 0;
}

Answer 1

对于您的限制，暴力破解应该足够快:n 最多有 19 位。生成所有具有 numDigits(n) 位的正整数。如果设置了k位，则删除与设置位对应的位置的数字。将结果与全局最优值进行比较，并在需要时进行更新。

复杂度:O(2^log n * log n)。虽然这可能看起来很多并且与 O(n) 渐近地相同，但实际上它会快得多，因为 O(2^log n * log n 中的对数) 是一个以 10 为底的对数，它将给出一个小得多的值(1 + log base 10 of n 给你 的位数n).

您可以通过每次生成 n - k 的 n 组合并构建由以下组成的数字来避免 log n 因子生成每个组合时选择的 n - k 位置(将其作为参数传递)。这基本上意味着您解决了类似的问题:给定 n，按顺序选择 n - k 位数字，使得结果数最大)。

注意:有一种不涉及暴力破解的方法可以解决这个问题，但我也想向 OP 展示这个解决方案，因为他在评论中询问如何使用暴力破解.对于最佳方法，研究如果我们从左到右逐位构建我们的数字会发生什么，并且对于每个数字 d，我们将删除所有当前选择的小于它的数字。我们什么时候可以删除它们，什么时候不能？