1 条题解
-
0
双端传送带 · 讲解
思路与接口
用
deque<long long>保存从左到右的当前顺序。push_front、push_back分别放入两端;front、back查询两端;pop_front、pop_back负责删除。在读取或弹出元素前先调用empty(),空容器输出EMPTY。REVERSE使用<algorithm>中的reverse(d.begin(), d.end()),将半开迭代器区间内的整个序列反转。空容器和只有一个元素的容器都可以安全调用。翻转以后继续直接使用 deque 的左右端接口即可。正确性
开始时 deque 和传送带都为空。假设某条指令前 deque 的元素顺序与传送带一致,左右放入、查询及删除显然对应同一端。
reverse反转每个元素的位置,也与指令定义一致。因此每条指令后仍保持同一顺序,所有输出均正确。复杂度
双端放入、删除、查询为 O(1)。一次翻转长为 L 的序列需要 O(L),并不是 O(1)。设全部翻转长度之和为 S,总时间 O(q+S),题目保证 S≤2000000;空间 O(q)。
常见错误
- 空 deque 上调用
front()、back()或弹出操作。 - 翻转时只交换第一个和最后一个元素,遗漏中间部分。
common_wrong.cpp展示该错误;最大规模翻转数据能拒绝它。 - 以为
REVERSE不改变后续操作所理解的左右端。 - 忽略
REVERSE的线性复杂度,错误估计总时间。
数据验证说明
Python 小数据与大数据答案使用 deque 配合逻辑方向标志,不实际翻转序列,从不同的实现路径验证 C++ 的实际翻转。校验器维护当前长度并严格累加每次翻转成本,包括恰好达到上限和超过上限的输入。
原创来源记录
本题题面、样例、代码、讲解与数据从零编写。只使用公开的算法概念和 C++ 标准库接口,没有使用第三方题面、故事、程序或测试文件。
C++17 参考实现
#include <algorithm> #include <deque> #include <iostream> #include <string> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int q; cin >> q; deque<long long> belt; while (q--) { string op; cin >> op; if (op == "LEFT" || op == "RIGHT") { long long x; cin >> x; if (op == "LEFT") belt.push_front(x); else belt.push_back(x); } else if (op == "REVERSE") { reverse(belt.begin(), belt.end()); } else if (belt.empty()) { cout << "EMPTY\n"; } else if (op == "POPL") { cout << belt.front() << '\n'; belt.pop_front(); } else if (op == "POPR") { cout << belt.back() << '\n'; belt.pop_back(); } else if (op == "FRONT") { cout << belt.front() << '\n'; } else { cout << belt.back() << '\n'; } } } - 空 deque 上调用
- 1
信息
- ID
- 5260
- 时间
- 2000ms
- 内存
- 256MiB
- 难度
- 1
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者