给定一个数字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;
}

- LearningMath

---

作为发布内容，这并不适合本网站。SO的目标是帮助解决具体问题，而不是提出想法。告诉我们你尝试了什么以及遇到了什么困难，我们才能提供帮助。 - Angew is no longer proud of SO

这不是作业，我正在为一场算法竞赛做准备，并在在线评测系统上解决问题。-- 你连尝试都没有就在做准备吗？ - Shoe

@J.M，你不可能完全没有任何想法。这个算法的暴力破解版本在逻辑和语法上都非常简单。 - Shoe

@trumpetlicks 我怀疑 任何 Stack Exchange 网站都不会接受一个完全没有研究努力的问题。 - Angew is no longer proud of SO

@trumpetlicks...如果问题确实显示出足够的研究努力（绝对比数学网站更多，可能略微，但不过度，比CS网站更合适（没有“算法”网站）），那么[so]肯定是合适的。 - Bernhard Barker

Answer 1

在最左边的 k+1 个数字中，找到最大的数字（假设它位于第 i 个位置。如果有多个相同的数字，选择最左边的那个）。保留这个数字。对于新的数字 k_new = k-i+1 和原始数字的第 i+1 到 n 个数字，重复这个算法。

Eg. k=5 and number = 7454982641
First k+1 digits: 745498
Best number is 9 and it is located at location i=5. 

new_k=1, new number = 82641
First k+1 digits: 82
Best number is 8 and it is located at i=1.

new_k=1, new number = 2641
First k+1 digits: 26
Best number is 6 and it is located at i=2

new_k=0, new number = 41
Answer: 98641

复杂度为O(n)，其中n是输入数字的大小。

编辑：正如iVlad提到的那样，在最坏情况下，复杂度可能是二次的。您可以通过维护大小不超过k+1的堆来避免这种情况，这将使复杂度增加到O(nlogk)。

- ElKamina

---

这是正确的，但如果您按降序排序输入，则复杂度为O(n^2)。您可以获得O(n)的复杂度。 - IVlad

维护堆仍会增加 log k 的因素。您需要使用栈来获得 O(n)。 - IVlad

我认为你想表达的是：找到最大值的第一个出现位置（因为它可能会重复出现）。 - Amrinder Arora

@AmrinderArora 是的。谢谢！ - ElKamina

Answer 2

暴力破解对于你的限制应该足够快：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 中选择 n-k 的组合，并在生成每个组合时构建由选择的 n-k 个位置组成的数字来避免 log n 因子（将其作为参数传递）。这基本上意味着您解决了类似的问题：给定 n，在顺序选择 n-k 个数字的情况下，使得所得到的数字最大）。

注意：有一种方法可以解决这个问题，而不涉及暴力破解，但我也想向 OP 展示这个解决方案，因为他在评论中问如何进行暴力破解。对于最佳方法，请调查如果我们从左到右逐位构建数字，并对于每个数字 d，我们将删除所有当前选定的小于它的数字。我们什么时候可以删除它们，什么时候不能删除？

- IVlad

---

你的意思是要使用位掩码吗？ - LearningMath

谢谢你的解释。 - LearningMath

Answer 3

以下内容可能有所帮助：

void removeNumb(std::vector<int>& v, int k)
{
    if (k == 0) { return; }
    if (k >= v.size()) {
        v.clear();
        return;
    }
    for (int i = 0; i != v.size() - 1; )
    {
        if (v[i] < v[i + 1]) {
            v.erase(v.begin() + i);
            if (--k == 0) { return; }
            i = std::max(i - 1, 0);
        } else {
            ++i;
        }
    }
    v.resize(v.size() - k);
}

- Jarod42