edu 156 div2 c

#include 
using namespace std;
using ll = long long;
void solve(){
    string s;
    cin>>s;
    //s =  s;
    ll t;
    cin>>t;
    //t--;
    ll pos,k;
    ll len = 0;
    for(int i = 0 ; i < s.length() ; i++){
        if(len + s.length() - i >= t){
            pos = t - len;//第几个字符
            k = i;//这段删除几个
            break;
        }else{
            len += s.length() - i;
        }
    }
    //cout<
    //每次先将前面的删掉 ， 先被删掉的应该是首个字典序小于的
    //如果s[i] < s[i-1]  就删掉 i - 1 是他目前存在的上一个
    string res;
    for(auto x : s){
        while (k > 0 && res.length() && x < res.back()){
            res.pop_back();
            k--;
        }
        res.push_back(x);
    }
 
    cout<1];
}
 
 
int main(){
    int t;
    cin>>t;
    while(t--){
        solve();
    }
}

先考虑如果让变化后的字符串最小，考虑

a b d a b c

观察到 再前面的位置使得字典序改变，字典序最小

当s[i] < s[i-1] 将i-1删除这样s[i] 就会到 i-1的位置

a b d a b c

a b a b c

观察删除后的字符串，发现并不需要从头开始计算，只需要从连接处在进行比较，

a b a b c

a a b c

可以通过一个单调栈进行维护，或者单链表也可以

计算一下最多删除多少个数