求长度为k的最小字典序子序列

1. 题目描述

   Max power

   Given a non-negative number , remove digits from the number so that the new number is as small as possible.

2. 输入描述

   There are multiple test cases.

   Each test case consists of two number, and , as described above.

3. 输出描述

   Output the smallest possible number for each test case in a single line. Remove the leading zeros.

4. 输入输出示例

   输入

   5
   1432219 3
   1011 1
   1234 1
   4321 1
   23333 2
   

   输出

   1219
   11
   123
   321
   233
   

思路

1. 删除 个字符，相当于选择 个字符，数值最小，可以转化成字典序最小，因此可以把题目转化成求长度为 的最小字典序子序列。
2. 令字符串为 ，令字符串 为 从 位置到 位置的连续片段，和均从开始。
3. 贪心的考虑，子序列的第一个字符为 的最小字符 ，设该字符的位置为 ，那么第二个字符为 的最小字符 ，且该字符的位置为，第三个字符为 的最小字符，依次类推。
4. 可以使用单调队列来维护，使得复杂度达到 。

代码实现

# include <cstdio>
# include <cstring>
# include <iostream>

using namespace std;

const int N = 10000 + 100;

char s[N];
int qu[N], ql, qr;

void popRight(int x) {
    while (qr > ql && s[qu[qr-1]] >= s[x]) qr --; 
}

int main(void) {
    int T, k;
    scanf("%d", &T);
    while (T -- ) {
        scanf("%s%d", s, &k);
        ql = qr = 0;
        int n = strlen(s);
        
        for (int i = 0; i <= k; i++) {
            popRight(i);
            qu[qr ++] = i;
        }
        
        int printed = 0;
        if (printed || s[qu[ql]] != '0') {
            printf("%c", s[qu[ql]]);
            printed = 1;
        }
        ql ++;
        for (int i = k + 1; i < n; i++) {
            popRight(i);
            qu[qr ++] = i;
            if (printed || s[qu[ql]] != '0') {
                printf("%c", s[qu[ql]]);
                printed = 1;
            }
            ql ++;
        }
        puts(printed ? "" : "0");
    }
    
    return 0;
}