1 条题解

  • 0
    @ 2026-11-11 23:35:27

    题意简述

    单窗口按编号顺序 FCFS 服务;轮到某同学时若"已等待时间严格大于耐心值"则直接离开(不占用窗口),否则立即开始打饭。统计:吃到饭人数、最后结束时刻、吃到饭者中的最大等待时间。

    思路

    分析

    没有任何调度决策(服务顺序题面已固定),直接顺序扫描,维护一个变量:

    • TT = 窗口空闲时刻,初始 00;
    • 对同学 ii:开始时刻 S=max⁡(T,ti)S = \max(T, t_i),等待时间 W=S−tiW = S - t_i;
      • 若 W>wiW > w_i:离开,TT 不变(他没占窗口);
      • 否则:人数 +1+1,T=S+ciT = S + c_i,并更新"最后结束时刻"与"最大等待时间"。

    为什么正确

    • 服务顺序由编号唯一确定,不存在贪心/DP 的选择空间;
    • 同学离开不推进 TT,窗口在他等待期间保持空闲,下一位同学的 SS 仍由 max⁡(T,ti)\max(T, t_i) 给出;
    • 每个同学的处理只依赖当前的 TT,与后面的人无关,顺序扫描即得全局结果。

    复杂度

    O(n)O(n) 时间、O(1)O(1) 额外空间。

    参考代码(C++)

    #include <cstdio>
    #include <algorithm>
    using namespace std;
    
    int main() {
        freopen("queue.in", "r", stdin);
        freopen("queue.out", "w", stdout);
    
        int n;
        if (scanf("%d", &n) != 1) return 0;
        long long freeTime = 0;    // 窗口空闲时刻
        long long served = 0;      // 吃到饭的人数
        long long lastFinish = 0;  // 最后一名吃到饭的同学的结束时刻
        long long maxWait = 0;     // 吃到饭的同学中的最大等待时间
        for (int i = 0; i < n; i++) {
            long long t, c, w;
            scanf("%lld %lld %lld", &t, &c, &w);
            long long start = max(freeTime, t);
            long long wait = start - t;
            if (wait > w) continue;  // 等待时间严格大于耐心值,直接离开
            served++;
            freeTime = start + c;
            lastFinish = freeTime;
            maxWait = max(maxWait, wait);
        }
        printf("%lld %lld %lld\n", served, lastFinish, maxWait);
        return 0;
    }
    

    易错点

    1. 严格大于:等待时间恰好等于耐心值时不离开(测试点 5、12 专门卡这一边界)。
    2. 离开同学的等待时间不计入第 3 项;若把所有人一起取 max,样例 2 会算出 33 而不是 22。
    3. 必须 long long:wiw_i 可达 101010^{10},且全员排队时结束时刻可达约 1.1×10101.1 \times 10^{10}。测试点 10 的输出是 100000 10000000001 9999900000,后两个数都超过 231−12^{31} - 1;测试点 9 的随机结果同样越界。用 int 只能得部分分。
    4. 无人吃到饭时后两项输出 00。本题 ti≥1t_i \ge 1 保证第一名同学等待必为 00、一定会吃到饭,但按题意写上防御逻辑更稳。
    5. 题面已保证 tit_i 非递减,直接按输入顺序处理即可;自己再排序反而可能破坏"同时到达按输入顺序"的约定(需 stable 才安全,不建议多此一举)。

    测试点设计

    测试点 设计意图
    1–2 题面样例
    3 n=1n=1
    4 t=109t = 10^9 的大时刻
    5 构造的等待链:第 2、3 人离开,第 4 人"等待恰等于耐心值"留下,第 5 人也恰好卡边界
    6 6 人同一时刻到达,等待依次为 0…50 \ldots 5
    7–9 随机数据(小 / 中 / 满规模,满规模含大 ww)
    10 全员 t=1t=1、c=105c=10^5、w=1010w=10^{10}:全部吃到饭,强制 long long
    11 10510^5 人挤在 [1,1000][1, 1000] 内到达、耐心普遍很小:先来者堵住窗口,后续大量离开
    12 等待恰等于 ww 的两点精确边界
    • 1

    信息

    ID
    3
    时间
    1000ms
    内存
    256MiB
    难度
    3
    标签
    递交数
    2
    已通过
    2
    上传者