题目重点:Applied Research OA 的仓库/服务器派送题:跳过禁用和满载实体,全部不可用时重置容量,统计接单数并处理无可用仓库。
题意与假设
这道练习题保留了面经中值得训练的核心约束,并将需要澄清的条件单独列出。现场拿到变体时,先和面试官确认这些条件。
- 主训练版每次配送从 0 搜索,按 0→n−1 顺序找未禁用且剩余容量>0; 的接续指针作为变体单独说明。
- 每次成功配送消耗 1 容量、累计仓库处理数+1;禁用是永久禁用,容量重置不重新启用。
- 若无仓库可用但至少有一个启用且初始容量>0,则重置所有启用仓库的剩余容量再重试一次;若所有均禁用/初始容量 0,返回无可派送状态而非死循环。
- 最高数同分返回最大索引;如果一件都未派,返回值依接口确认,训练版可返回 -1。
解题路线
- 明确 `delivery` 与 `disable(index)` 操作格式、搜索起点是否接续、重置是否恢复禁用、处理不了包裹时是报错还是跳过。
- 初始化 remaining=capacity、disabled=false、handled=0;处理禁用只更新标志,不改历史 handled。
- 配送时按约定起点环扫最多 n 次,找到可用者扣容量并加 handled;找不到就检查是否存在启用且初始容量正的仓库,再重置可用实体容量并最多重试一次。
- 结束用 (-handled,-index) 取最大,或扫描中 `handled[i]>bestCount 或 == 且 i>bestIndex`;不要按剩余容量评选。
- 若输入量很大,可维护可用索引有序集合与轮转 epoch;但重置、禁用会改变集合,先以简单模拟对照验证。
手动走一遍
训练 capacity=[1,2],三次配送从 0 搜索:第 1 次给 0、第 2/3 次给 1,handled=[1,2],返回 1。再禁用 1,后续 0 满时重置 0 的容量后派给 0,disabled 的 1 不复活。若两者都禁用,再来配送必须停止。接续游标变体的前几次分配可不同。
规模与取舍
n 个仓库、d 条日志的朴素实现每次派送最多两圈 O(n),总 O(dn) 时间、O(n) 状态空间;维护可用集合可将常规查找降至 O(log n),重置需按仓库数处理或用 epoch 惰性策略。
易错点与追问
容易失分的边界
- 所有仓库永久禁用时反复 reset 导致无限循环。
- reset 把 disabled 也清除。
- 按剩余容量或处理次数最少分配,违背轮转规则。
- 同分返回最小索引。
- 把每次从 0 与接续指针两个帖的描述混为固定原题。
继续深挖
- 每次从上次位置继续时如何维护指针?
- 重置是否只在容量全部耗尽时发生?
- 禁用仓库已处理的数量是否仍计最终排名?
- 百万仓库/日志时怎样用有序集合或批量跳过?
