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

古城微笑少年丶 2024-03-16 14:53 55阅读 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 条评论，55人围观）

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

相关阅读

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

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

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

相关代码源每日一题div1 枚举倍数优美！最长上升子序列

[优美！最长上升子序列 - 题目 - Daimayuan Online Judge][- _ - Daimayuan Online Judge] 题意： ![6f04eef

悠悠/ 2024年03月31日 12:47/ 0 赞/ 46 阅读

相关代码源每日一题div1 枚举倍数平方计数

[平方计数 - 题目 - Daimayuan Online Judge][- _ - Daimayuan Online Judge] 题意： ![4599c5d594734

小灰灰/ 2024年03月31日 12:35/ 0 赞/ 57 阅读

相关代码源每日一题div1 【哈希DP】连续子序列

[连续子序列 - 题目 - Daimayuan Online Judge][- _ - Daimayuan Online Judge] 题意： ![824f6dcd63de

た入场券/ 2024年03月31日 11:44/ 0 赞/ 66 阅读

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

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

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

相关【状压DP】代码源每日一题div1 环的数量

namo，根本学不会状压DP [环的数量 - 题目 - Daimayuan Online Judge][- _ - Daimayuan Online Judge

素颜马尾好姑娘i/ 2024年03月24日 14:26/ 0 赞/ 6 阅读

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

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

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

相关【GCD枚举因子+环上问题】代码源每日一题div1 最大公约数

[最大公约数 - 题目 - Daimayuan Online Judge][- _ - Daimayuan Online Judge] 题意： ![52f69b018338

怼烎@/ 2024年03月16日 16:40/ 0 赞/ 49 阅读

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

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

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

相关 leetcode 155. 最小栈单调栈

一个正常的栈，一个最小栈栈顶是当前栈的最小元素 push的时候如果push的x比最小栈顶的小就push x 否则吧栈顶再push一遍 include <iost

素颜马尾好姑娘i/ 2022年02月17日 05:11/ 0 赞/ 331 阅读