CF1066C 题解
2022/8/26 6:23:38
本文主要是介绍CF1066C 题解,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
前言
题目传送门!
更好的阅读体验?
本题是简单的双端队列练手题。
思路
题意大致如下:
- 执行双端队列
push_front()
操作。 - 执行双端队列
push_back()
操作。 - 查询 \(\min\{mp_x - L, R - mp_x\}\),其中 \(mp_x\) 表示 \(x\) 元素的对应下标。
由于 STL 配备的双端队列性能较差,使用数组模拟队列。
每次压元素时,记录 \(mp_x\)。输出直接依照上面的式子即可。
需要注意 push_front()
可能使得队列下标越界,解决方法是将 \(L\) 与 \(R\) 赋予较大值。
实际不需要实现队列,只需记录 \(mp_x\)。
代码
#include <cstdio> #include <iostream> using namespace std; void fastio() { ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); } const int N = 2e5; int mp[N << 1 + 5], l = N+1, r = N; //原本是 l=1 与 r=0,补后变为 l=N+1 与 r=N。 int main() { fastio(); int Q; cin >> Q; while (Q--) { char op; int x; cin >> op >> x; if (op == 'L') mp[x] = --l; else if (op == 'R') mp[x] = ++r; else if (op == '?') cout << min(mp[x] - l, r - mp[x]) << '\n'; } return 0; }
希望能帮助到大家!
首发:2022-07-20 09:50:42
这篇关于CF1066C 题解的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 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功能效果提升
- 2024-05-08代码报错不用愁,CodeGeeX一键完成代码修复、错误解释的功能上线了!
- 2024-05-08今天开始程序员不用再发愁写commit message了,全部由CodeGeeX自动完成!