计蒜客- 2019计蒜之道D

计蒜客- 2019计蒜之道D. “星云系统”（单调队列/单调栈）

题意：

现在给定你一个字符串 $s$ 以及一个整数 $k$ ，请求出 $s$ 的字典序最小的长度为 $k$ 的子序列。

数据范围：

$0 < k \leq ∣ s ∣ \leq 5000000$

样例输入：

helloworld
5

样例输出：

ellld

思路：

假如我们先不考虑长度为k的限制我们应当怎么做？

我们以样例为例子。从左到右扫描字符串一遍：h、然后e，因为e的字典序比h小所以h不应该在e前面，所以把h删去，此时待选序列只有e；然后扫描l、l、o、r，此时待选序列中有ellor；然后扫描l，因为r比l大，所以r不应该在l之前，把r删除，同样o也是如此，现在待选序列就只剩elll；然后扫描d。按照前面的原理，所以elll都删去，现在待选序列中只有d。

不过前面的部分是否有些似曾相识，这不是符合单调栈的性质吗。所以前面的问题我们可以用单调栈来解决。

那么现在有了长度为k的限制，我们应该怎么做？

首先我们发现，假如字符串长度为n，那么想要答案最优就要从第1~(n-k+1)中取一个最小的字母。这个就相当于从单调栈中取栈底的元素，并删去（这个位置以及这个位置之前的都不能用了，但因为这个位置之前的在单调栈中不存在，故只删除这一个即可）。接下来取第二个字符，那么就是将第（n-k+2）加入单调栈，然后从单调栈中栈底元素并从单调栈删去。从单调栈中取栈底元素其实就是单调队列。

代码：

#include<bits/stdc++.h>
#define mset(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
char s[5000000+10],st[5000000+10],ans[5000000+10];
int main()
{
    int k,p,top,ls;
    scanf("%s%d",s+1,&k);
    p=0,top=0;//p指向st队头
    ls=strlen(s+1);
    int w=ls-k+1;
    for(int i=1;i<=w;++i){//初始化，先找出(1~n-k+1)中字典序最小的字符串
        while(top>0&&s[i]<st[top-1]) top--;
        st[top++]=s[i];
    }
    int cnt=0;
    ans[cnt++]=st[p++];//取出栈底字符作为答案的第一个字符。
    for(int i=w+1;i<=ls;++i){//取剩下的k-1个字符
        while(top>p&&s[i]<st[top-1]) top--;
        st[top++]=s[i];
        ans[cnt++]=st[p++];
    }
    ans[cnt]='\0';
    printf("%s\n",ans);
    return 0;
}

单调队列用deque实现：

#include<bits/stdc++.h>
#define mset(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
string s,ans;
deque<char> st;
int main()
{
    int k;
    ios::sync_with_stdio(false);cin.tie(0);
    cin>>s>>k;
    int w=s.length()-k;
    for(int i=0;i<=w;++i)
    {
        while(!st.empty()&&s[i]<st.back()) st.pop_back();
        st.push_back(s[i]);
    }
    ans+=st.front();
    st.pop_front();
    for(int i=w+1;i<s.length();++i){
        while(!st.empty()&&s[i]<st.back()) st.pop_back();
        st.push_back(s[i]);
        ans+=st.front();
        st.pop_front();
    }
    cout<<ans<<endl;
    return 0;
}