1 条题解
-
0
题意简述
单窗口按编号顺序 FCFS 服务;轮到某同学时若"已等待时间严格大于耐心值"则直接离开(不占用窗口),否则立即开始打饭。统计:吃到饭人数、最后结束时刻、吃到饭者中的最大等待时间。
思路
分析
没有任何调度决策(服务顺序题面已固定),直接顺序扫描,维护一个变量:
- = 窗口空闲时刻,初始 ;
- 对同学 :开始时刻 ,等待时间 ;
- 若 :离开, 不变(他没占窗口);
- 否则:人数 ,,并更新"最后结束时刻"与"最大等待时间"。
为什么正确
- 服务顺序由编号唯一确定,不存在贪心/DP 的选择空间;
- 同学离开不推进 ,窗口在他等待期间保持空闲,下一位同学的 仍由 给出;
- 每个同学的处理只依赖当前的 ,与后面的人无关,顺序扫描即得全局结果。
复杂度
时间、 额外空间。
参考代码(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; }易错点
- 严格大于:等待时间恰好等于耐心值时不离开(测试点 5、12 专门卡这一边界)。
- 离开同学的等待时间不计入第 3 项;若把所有人一起取 max,样例 2 会算出 而不是 。
- 必须 long long: 可达 ,且全员排队时结束时刻可达约 。测试点 10 的输出是
100000 10000000001 9999900000,后两个数都超过 ;测试点 9 的随机结果同样越界。用 int 只能得部分分。 - 无人吃到饭时后两项输出 。本题 保证第一名同学等待必为 、一定会吃到饭,但按题意写上防御逻辑更稳。
- 题面已保证 非递减,直接按输入顺序处理即可;自己再排序反而可能破坏"同时到达按输入顺序"的约定(需 stable 才安全,不建议多此一举)。
测试点设计
测试点 设计意图 1–2 题面样例 3 4 的大时刻 5 构造的等待链:第 2、3 人离开,第 4 人"等待恰等于耐心值"留下,第 5 人也恰好卡边界 6 6 人同一时刻到达,等待依次为 7–9 随机数据(小 / 中 / 满规模,满规模含大 ) 10 全员 、、:全部吃到饭,强制 long long 11 人挤在 内到达、耐心普遍很小:先来者堵住窗口,后续大量离开 12 等待恰等于 的两点精确边界
- 1
信息
- ID
- 3
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 3
- 标签
- 递交数
- 2
- 已通过
- 2
- 上传者