题目描述

难度分:$1600$

输入$T(\leq 10^4)$表示$T$组数据。所有数据的字符串长度之和$\leq 10^6$。

每组数据输入长度$\leq 10^6$的字符串$s_1$（只包含小写字母）和下标$pos(1 \leq pos \leq \frac{n \times (n+1)}{2}, n=len(s))$。

• 从$s_1$去掉一个字母，得到的字典序最小的字符串，记作$s_2$。
• 从$s_2$去掉一个字母，得到的字典序最小的字符串，记作$s_3$。

依此类推，直到剩下一个字母，此时的字符串记作$s_n$。

输出$s_1+s_2+…+s_n$的第$pos$个字母。

你只需要输出一行，这一行的第$i$个字母对应第$i$组数据的答案。请勿添加空格。

输入样例

3
cab
6
abcd
9
x
1

输出样例

abx

算法

贪心

错了好几发，结果发现是爆$int$了，贪心思路还是比较容易想到的：

1. 先从前往后删字母，目的是让$s$串单调不减。这个可以用栈来实现，一旦碰到$s[stk.top()] \gt s[i]$（$stk$为栈），就删除栈顶的下标，直到这个条件不满足，再把$i$压栈。之所以要从前往后考虑，就是字典序是从前往后比较的，要尽量先让前面保持单调不减。

2. 得到单调不减的串后，再从后往前删下标，把后面会让字典序更大的字符删掉。

由于要求的是$s_1+s_2+…s_n$的第$pos$个下标，$s_1$长度为$n$，$s_2$长度为$n-1$，……，$s_i$长度为$n-i+1$。先用二分计算出第几个串可以覆盖住$pos$位置，假设是第$r$个串，然后用$pos$减去前$r-1$个串的长度，从最后一个串中找到第$pos$个位置即可。

利用以上的贪心策略构造最后一个串，先进行步骤$1$的贪心，用一个$del$数组标记被删除过的下标，直到删除了$r-1$个字母。如果走完步骤$1$的操作后还没有删除够$r-1$个字符，就继续步骤$2$的贪心，直到删除了$r-1$个字符。最后没有被标记的位置按照原串顺序连接起来，就是第$r$个串的字符。

复杂度分析

时间复杂度

二分求出$r$的时间复杂度是$O(log_2n)$；构造第$r$个串在最差情况下需要遍历字符串$s$三次，一次进行步骤$1$的贪心，一次进行步骤$2$的贪心，最后一次用没被删除的字符构建出$s_r$。因此，整个算法的时间复杂度为$O(n)$。

空间复杂度

除去输入的字符串$s$，栈空间的消耗是$O(n)$（最差情况下会压入$O(n)$个下标），构造出的$s_r$占用空间是$O(n)$，标记数组$del$占用空间也是$O(n)$。因此，算法整体的额外空间复杂度也为$O(n)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <stack>

using namespace std;
typedef long long LL;

const int N = 1000010;
char s[N], t[N];
bool del[N];
int T;
LL n, x;

LL sum(int i) {
    int a1 = n, ai = n + 1 - i;
    return (LL)(a1 + ai)*i/2;
}

int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%s", s + 1);
        n = strlen(s + 1);
        for(int i = 1; i <= n; i++) {
            del[i] = false;
        }
        scanf("%lld", &x);
        int l = 1, r = n;
        while(l < r) {
            LL mid = l + r >> 1;
            if(sum(mid) >= x) {
                r = mid;
            }else {
                l = mid + 1;
            }
        }
        int cnt = 0;
        // 第r个串拼接在后面才能覆盖位置x
        stack<int> stk;
        for(int i = 1; i <= n && cnt < r - 1; i++) {
            while(!stk.empty() && cnt < r - 1 && s[stk.top()] > s[i]) {
                del[stk.top()] = true;
                stk.pop();
                cnt++;
            }
            stk.push(i);
        }
        for(int i = n; i >= 1 && cnt < r - 1; i--) {
            if(!del[i]) {
                del[i] = true;
                cnt++;
            }
        }
        for(int i = 1, j = 1; i <= n; i++) {
            if(!del[i]) {
                t[j++] = s[i];
            }
        }
        int pos = x - sum(r - 1);
        printf("%c", t[pos]);
    }
    return 0;
}