P1106 删数问题

P1106 删数问题
这题用双端队列做才是首选，贪心的思路很好理解，我们只有 次删除机会，每次删除都应该让前面的数尽可能地小，因为前面是高位，权重更高。

所以可以这样处理，维护一个单调不减的双端队列，遍历数组，若队列不为空且当前数小于队尾，而且有删除次数，则消耗一次删除次数弹出队尾（因为有了更小的选择），最后将当前数加到队尾。

遍历完成后可能会出现还有删除次数的情况（数组本身趋向于单调不减，遍历过程中很少满足弹出队尾的条件），这时进行相应次数的弹出队尾操作即可。

最后就是去除前导 和输出，下面列出的是本题的数据强化版U83355 删数问题【升级版】的AC代码，这个版本卡掉了 的算法，我所知的可行的做法就是 的 表和本题解的 的做法。

#include <cstdio>
#include <cstring>
#include <deque>

using namespace std;

const int N = 5e5 + 5;
char a[N];
int n, k;

void solve() {
    scanf("%s%d", a, &k);
    n = strlen(a);
    
    deque<char> dq;
    for (int i = 0; i < n; i++) {
        while (!dq.empty() && a[i] < dq.back() && k) {
            dq.pop_back();
            k--;
        }
        dq.emplace_back(a[i]);
    }
    
    while (k--) dq.pop_back();
    while (!dq.empty() && dq.front() == '0') dq.pop_front();    // 去除前导 0
    
    if (dq.empty()) putchar('0');
    while (!dq.empty()) {
        putchar(dq.front());
        dq.pop_front();
    }
    putchar('\n');
}

int main() {
    int t; scanf("%d", &t);
    while (t--) solve();
    return 0;
}