NC14893 栈和排序
2022/7/2 6:20:20
本文主要是介绍NC14893 栈和排序,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
NC14893 栈和排序
题目
题目描述
给你一个1->n的排列和一个栈,入栈顺序给定
你要在不打乱入栈顺序的情况下,对数组进行从大到小排序
当无法完全排序时,请输出字典序最大的出栈序列
输入描述
第一行一个数 \(n\)
第二行 \(n\) 个数,表示入栈的顺序,用空格隔开,结尾无空格
输出描述:
输出一行 \(n\) 个数表示答案,用空格隔开,结尾无空格
示例1
输入
5 2 1 5 3 4
输出
5 4 3 1 2
说明
2入栈;1入栈;5入栈;5出栈;3入栈;4入栈;4出栈;3出栈;1出栈;2出栈
题解
思路
知识点:栈,预处理。
要得到最大字典序,那就要尽可能让大的数字靠前。由于栈是先进先出的,可以有限地控制一段序列顺序。如果一个元素,他之后没有更大的元素,入栈以后就必须出栈,否则他必然会在比他小的元素之后出栈,不是最优;如果有更大元素则不能出栈,不然大元素无法在前面,也不是最优的。
对此,我们需要知道第 \(i\) 个元素及以后的最大值,即后缀最大值 \(maxa[i]\)。对第 \(i\) 个元素,先入栈 \(s\),若\(s.top() < max[i+1]\) 则出栈,否则不出栈。
时间复杂度 \(O(n)\)
空间复杂度 \(O(n)\)
代码
#include <bits/stdc++.h> using namespace std; stack<int> s; int a[100007], maxa[100007]; int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int n; cin >> n; for (int i = 0;i < n;i++) cin >> a[i]; for (int i = n - 1;i >= 0;i--) maxa[i] = max(a[i], maxa[i + 1]); for (int i = 0, j = 0;i < n;i++) { s.push(a[i]); while (!s.empty() && maxa[i + 1] < s.top()) cout << s.top() << ' ', s.pop(); } while (!s.empty()) cout << s.top() << ' ', s.pop(); return 0; }
这篇关于NC14893 栈和排序的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升