原题链接
题意：
给出一个长度为n的序列和k，要求选出一个最短的子序列使得该子序列包含1~k所有数并且字典序最小。
思路：
一开始也想到单调栈了，然后用deque模拟一直没过。
大体思路就是：
如果当前栈为空的话，直接入栈；
如果不为空的话，考虑栈顶元素和当前元素的关系，如果栈顶元素大于当前元素并且栈顶元素在后面还有的话，就弹出栈顶元素，因为可以用后面的元素来替代这个元素。
最后倒着把序列输出就可以了。
代码：
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<ll,ll>PLL; typedef pair<int,int>PII; typedef pair<double,double>PDD; #define I_int ll inline ll read() { ll x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-')f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=x*10+ch-'0'; ch=getchar(); } return x*f; } #define read read() #define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0) #define multiCase int T;cin>>T;for(int t=1;t<=T;t++) #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i<(b);i++) #define per(i,a,b) for(int i=(a);i>=(b);i--) #define perr(i,a,b) for(int i=(a);i>(b);i--) ll ksm(ll a,ll b,ll p) { ll res=1; while(b) { if(b&1)res=res*a%p; a=a*a%p; b>>=1; } return res; } #define PI acos(-1) const double eps=1e-8; const int maxn=1e6+100; int a[maxn],n,k,vis[maxn],cnt[maxn]; stack<int>stk; int main(){ n=read,k=read; rep(i,1,n){ a[i]=read; cnt[a[i]]++; } rep(i,1,n){ cnt[a[i]]--; if(vis[a[i]]) continue; while(!stk.empty()&&cnt[stk.top()]&&stk.top()>a[i]){ vis[stk.top()]=0; stk.pop(); } stk.push(a[i]); vis[a[i]]=1; } int idx=0; while(!stk.empty()){ a[++idx]=stk.top(); stk.pop(); } for(int i=idx;i;i--){ cout<<a[i]<<" "; } return 0; }
