同字形结构布局网站,js wordpress 菜单管理系统,e龙岩服务平台,设计云网站建设题意#xff1a;
给你一个整数列表 x1#xff0c;x2#xff0c;#xff0c;… #xff0c;xn 和一个数字 k#xff0c;它保证从1到 k 的每个 i 至少出现在列表中一次。 现在求一个字典序最小的子序列#xff0c;子序列有1到k组成
题解#xff1a;
单调栈求解 我们先…题意
给你一个整数列表 x1x2… xn 和一个数字 k它保证从1到 k 的每个 i 至少出现在列表中一次。 现在求一个字典序最小的子序列子序列有1到k组成
题解
单调栈求解 我们先预处理求出每种数最后出现的位置用数组suf存 比如这10个数54321411155 suf[1] 8 suf[2] 4 suf[3] 3 suf[4] 6 suf[5] 10 我们设一个栈每次读入新的数据x第i位时与栈顶元素top比较如果栈顶元素大于x且suf[top]i,我们就将栈顶弹出直到该条件不满足或者栈为空然后将数据x存入栈内 原因 如果suf[top]i说明在当前x的后面还会有和栈一样大小的数而且栈顶大于x我们为了让字典序更小就可以用组合x top代替 top x 就比如说5 4 5 我们栈顶为5第一个元素读入第二个元素4,4比5小且4之后还有5第三个元素说明可以组成字典序更小的4 5而不是5 4所以将5第一个元素弹出将4存入
代码
#includebits/stdc.h
typedef long long ll;
using namespace std;
inline int read(){int s0,w1;char chgetchar();while(ch0||ch9){if(ch-)w-1;chgetchar();}while(ch0ch9) ss*10ch-0,chgetchar();//s(s3)(s1)(ch^48);return s*w;
}const int maxn2e59;
ll a[maxn];
int vis[maxn];
int st[maxn],suf[maxn];
ll n,m;
int main(){cinnm;for(int i1;in;i) a[i]read();int s 0;for(int i1;in;i) suf[a[i]] i;for(int i1;in;i){if(vis[a[i]]) continue;while(s a[i]a[st[s]] suf[a[st[s]]]i) //如果栈顶元素大于当前元素且栈顶元素后面还会出现 vis[a[st[s--]]] 0;//出栈并标记为空 st[s] i;vis[a[i]] 1;}for(int i1;im;i)printf(%lld ,a[st[i]]);printf(\n);return 0;
}
