【单调栈】代码源每日一题div1 字典序最小

古城微笑少年丶 2024-03-16 14:53 49阅读 0赞

[字典序最小 - 题目 - Daimayuan Online Judge][- _ - Daimayuan Online Judge]

题意：

![4deb970b024f4af798c6ade04c88cd47.png][]

思路：

因为是字典序最小，所以要尽可能是\[1,2,3,....N\]

考虑用单调栈维护这个子序列

枚举ai，当栈里的元素大于ai时且该位置后面还有这个数时弹出

为什么是这样，如果后面没有这个数，说明就不满足每个数出现一次的条件了

所以我们需要维护每个数出现的最后一个位置

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=1e6+10;
    const int mxe=1e6+10;
    
    int M,N;
    int a[mxn],last[mxn],is[mxn];
    
    void solve(){
    	cin>>M>>N;
    	for(int i=1;i<=M;i++){
    		cin>>a[i];
    		last[a[i]]=i;
    	}
    	stack<int> S;
    	for(int i=1;i<=M;i++){
    		if(is[a[i]]) continue;
    		while(!S.empty()&&S.top()>a[i]&&last[S.top()]>i){
    			is[S.top()]=0;
    			S.pop();
    		}
    		S.push(a[i]);
    		is[a[i]]=1;
    	}
    	vector<int> V;
    	while(!S.empty()){
    		V.push_back(S.top());
    		S.pop();
    	}
    	reverse(V.begin(),V.end());
    	for(int i=0;i<V.size();i++) cout<<V[i]<<" \n"[i==V.size()-1];
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;//cin>>__;
    	while(__--)solve();return 0;
    }

[- _ - Daimayuan Online Judge]: http://oj.daimayuan.top/problem/608
[4deb970b024f4af798c6ade04c88cd47.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/4f0f52855ae74f8d9c062fd9331a559b.png

发表评论取消回复

表情：

评论列表（有 0 条评论，49人围观）

还没有评论，来说两句吧...

相关阅读

相关代码源每日一题div1 DP 数组划分

[数组划分 - 题目 - Daimayuan Online Judge][- _ - Daimayuan Online Judge] 题意： ![3df804eb4f5b4

向右看齐/ 2024年03月31日 13:09/ 0 赞/ 41 阅读

相关代码源每日一题div1 贪心线性筛最小生成数

[最小生成数 - 题目 - Daimayuan Online Judge][- _ - Daimayuan Online Judge] 题意： ![471a3025205c

柔情只为你懂/ 2024年03月31日 12:49/ 0 赞/ 53 阅读

相关【最坏贪心】代码源每日一题div1 排列 2023.02.03

[排列 - 题目 - Daimayuan Online Judge][- _ - Daimayuan Online Judge] 今天牛牛完结撒花辣！但是我还没补完题，感觉这

短命女/ 2024年03月27日 13:01/ 0 赞/ 48 阅读

相关【代码源每日一题div1】树状数组数数

就是把权值树状数组反过来，感觉很妙啊 [数数 - 题目 - Daimayuan Online Judge][- _ - Daimayuan Online Judge] 题意

蔚落/ 2024年03月26日 19:46/ 0 赞/ 43 阅读

相关【代码源每日一题div1 二分答案】质区间长度

写一下之前写过的题的题解感觉篮球杯难度 [质区间长度 - 题目 - Daimayuan Online Judge][- _ - Daimayuan Online Judg

忘是亡心i/ 2024年03月26日 19:18/ 0 赞/ 55 阅读

相关【小DS】代码源每日一题div2 上帝的集合

根本不会 [上帝的集合 - 题目 - Daimayuan Online Judge][- _ - Daimayuan Online Judge] 题意： ![110f01

╰+攻爆jí腚メ/ 2024年03月16日 18:37/ 0 赞/ 21 阅读

相关【贪心】代码源每日一题div2 背包

[背包 - 题目 - Daimayuan Online Judge][- _ - Daimayuan Online Judge] 题意： ![c70769545d9f444

浅浅的花香味﹌/ 2024年03月16日 18:13/ 0 赞/ 52 阅读

相关【单调栈】代码源每日一题div1 字典序最小

[字典序最小 - 题目 - Daimayuan Online Judge][- _ - Daimayuan Online Judge] 题意： ![4deb970b024f

古城微笑少年丶/ 2024年03月16日 14:53/ 0 赞/ 50 阅读

相关【状态设计优化DP】代码源每日一题div1 等差数列

[等差数列 - 题目 - Daimayuan Online Judge][- _ - Daimayuan Online Judge] 题意： ![64f437cfde1a4

我就是我/ 2024年03月16日 14:48/ 0 赞/ 30 阅读

相关每日一题-155. 最小栈(20200512)

今天是2020年5月12日，星期二，也有好几天没写每日一题，继续捡起来了。题目描述设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的

古城微笑少年丶/ 2023年03月13日 06:20/ 0 赞/ 5 阅读