1 条题解

  • 0
    @ 2026-11-16 20:48:26

    双端传送带 · 讲解

    思路与接口

    用 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';
            }
        }
    }
    
    
    • 1

    信息

    ID
    5260
    时间
    2000ms
    内存
    256MiB
    难度
    1
    标签
    递交数
    1
    已通过
    1
    上传者