题解：UVA11491 奖品的价值 Erasing and Winning

· · 题解

题目传送门：UVA11491 奖品的价值 Erasing and Winning

upd on October 12, 2024：之前的代码超时了，现代码使用 STL 库中函数以优化程序，现在的代码保证 AC。

题目大意：

在长度为 N 的数中删除 D 个数字，使得剩下的数最大。

分析：

这道题目容易有个误区，就是应该删较小的数，保留较大的数，这是错误的。

比如这组数：

6 \ \ \ 2 \ \ \ 129199

如果保留较大的数，就得到 2999 ，实际上有更大的数为 9199 ，所以可以得出应该让高位的数尽可能大，即让“大数往前来，小数边上靠”。

就拿 6 \ \ \ 4 \ \ \ 579426 作为例子，不难看出：

第一次删 5 。

第二次删 7 。

第三次删 4 。

第四次删 2 。

剩下的数就是 96 。

我们是如何实现的呢？

第一次删 5 ，因为 5 \textcolor{red}{<} 7 。

第二次删 7 ，因为 7 \textcolor{red}{<} 9 。

第三次删 4 ，因为 4 \textcolor{red}{<} 6 。

第四次删 2 ，因为 2 \textcolor{red}{<} 6 。

然后我们就发现每次删掉的数都是比后一个小的数。

算法：

如果 a_i \le a_{i+1} ，就将 a_i 删除（当 i = n 时，就让 a_n 与 a_1 进行比较，删除较小数）。 a 指原数转化成的数组形式。如果没有减够，就从头再来一遍。

代码：

最后附上自己的代码：

#include <bits/stdc++.h>
using namespace std;

void solve(int n, int d, string num) {
    vector<int> s;
    for (char digit : num) {
        int value = digit - '0';
        while (d > 0 && !s.empty() && s.back() < value) {
            s.pop_back();
            d--;
        }
        s.push_back(value);
    }
    while (d-- > 0 && !s.empty()) {
        s.pop_back();
    }
    if (s.empty()) {
        cout << "0" << endl;
        return;
    }
    for (int i = 0; i < s.size(); ++i) {
        if (i > 0) cout << "";
        cout << char(s[i] + '0');
    }
    cout << endl;
}

int main() {
    while (true) {
        int n, d;
        cin >> n >> d;
        if (n == 0 && d == 0) {
            return 0;
        }
        string num;
        cin >> num;
        solve(n, d, num);
    }
    return 0;
}