NC17059 队列Q
NC17059 队列Q
题目
题目描述
ZZT 创造了一个队列 Q。这个队列包含了 N 个元素,队列中的第 i 个元素用 \(Q_i\) 表示。Q1 表示队头元素,\(Q_N\) 表示队尾元素。队列中的元素是 N 的一个全排列。
ZZT 需要在这个队列上执行 P 次操作,操作分两种:
FIRST X: 将元素 X 移到队头。
LAST X: 将元素 X 移到队尾。
在 P 次操作之后,ZZT 想知道队列中的元素的排列方式,由于他最近很忙,因此需要请你帮他解决这个问题。
输入描述
第一行输入一个正整数 N,表示队列的大小。
第二行输入 N 个正整数,\(Q_1, Q_2, Q_3, ... ..., Q_N\),\(Q_i\) 表示队列中的第 i 个元素。保证这 N 个数是 N 的一个全排列。
第三行输入一个正整数 P,表示接下来要进行的操作次数。
接下来 P 行,第 i 行输入一个字符串 \(S_i\) 以及一个正整数 \(X_i\),表示一次操作。
\(1 ≤ N ≤ 10_5\).
\(1 ≤ Q_i ≤ N\).
\(1 ≤ P ≤ 10^5\).
\(S_i\in\) { “FIRST”, “LAST” }.
\(1 ≤ X_i ≤ 10^5\).
输出描述
输出 N 个正整数,表示 P 次操作之后的队列。
示例1
输入
4
4 2 1 3
3
FIRST 4
LAST 2
LAST 1
输出
4 3 2 1
题解
思路
知识点:队列。
如果是没操作过的原序列的元素,相对位置不会改变,而操作过的元素绝对不会出现在没操作过的元素中间,因为每次都是往队列两端插入,不可能到中间。
一个元素的最终位置,取决于最后一次操作的时间和操作方式,因为最后一次操作产生的位置不会被之前所有操作以及其他元素除了最后一次操作之外的操作影响。并且最后操作时间早的元素先确定位置。
因此保存每个时间操作的元素 \(xi\) 和方式 \(opi\) 以及每个元素最后的操作时间 \(vis\) 。从小到大遍历时间 \(i\) ,若 \(vis[xi[i]] = i\) ,即这个时间就是这个元素最后操作的时间,根据操作 \(opi[i]\) ,结合 \(deque\) 进行操作,最后输出即可。
时间复杂度 \(O(n+p)\)
空间复杂度 \(O(n)\)
代码
#include <bits/stdc++.h>
using namespace std;
int a[100007];
int vis[100007], xi[100007], opi[100007];
deque<int> dq;
///元素位置由最后一次操作决定
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];
int p;
cin >> p;
for (int i = 1;i <= p;i++) {
string op;
int x;
cin >> op >> x;
vis[x] = i;
xi[i] = x;
opi[i] = op == "FIRST";
}
for (int i = 0;i < n;i++) {
if (!vis[a[i]]) dq.push_back(a[i]);
}
for (int i = 1;i <= p;i++) {
if (vis[xi[i]] == i) {
if (opi[i]) dq.push_front(xi[i]);
else dq.push_back(xi[i]);
}
}
for (int i = 0;i < n;i++) cout << dq[i] << ' ';
cout << '\n';
return 0;
}
最新文章
- C#遍历DataSet中数据的几种方法总结
- android版高仿淘宝客户端源码V2.3
- 根本没有“JSON“对象这回事(读汤姆大叔博文记录)
- 数组内部对象排序(sort)
- 单例模式(oc)
- Maven使用常见问题整理
- css 前景色与背景色
- POJ 3565 Ants (最小权匹配)
- 使用CURL发彩信,短信和进行多线程
- Java_io体系之BufferedWriter、BufferedReader简介、走进源码及示例——16
- Git管理工具对照(GitBash、EGit、SourceTree)
- CodeForces 327C
- Vue.js组件之同级之间的通信
- C++ protected访问权限思考
- Kilani and the Game-扩散形式的搜索
- C#任务同步
- MySQL开发——【字段类型、约束】
- Study之2 Glance相关操作-devstack
- 让cxGrid像Excel那样高亮显示选区的行号列标
- Java基础加强之并发(三)Thread中start()和run()的区别
热门文章
- 2021.12.06 P2508 [HAOI2008]圆上的整点(数论+ π )
- 2021.11.05 eleveni的水省选题的记录
- Dom基础(二):Dom性能优化
- Ubuntu 20.0.4 安装 NVIDIA N卡 驱动 画面撕裂 解决方法
- mosquitto服务器的安装以及mqtt.fx软件的使用
- 【openstack】红帽公开课笔记内容openstack
- OpenHarmony 3.1 Beta版本关键特性解析——分布式DeviceProfile
- 一次不规范HTTP请求引发的nginx响应400问题分析与解决
- XCTF练习题---MISC---pdf
- VMware16搭建Ubuntu22.04,更新为国内下载源,安装open-vm-tools,用SecureCRT远程连接