G. 厨师与粥 详细题解

题目核心理解

有 $n$ 个学生在队列中等待厨师分粥，厨师会持续分粥 $D$ 分钟。 每分钟开始时，厨师给当前队首学生一份粥； 学生在第 $x$ 分钟开始领到粥后，会在第 $x+s_i$ 分钟结束时返回队列。

学生返回规则：

1. 按优先级 $k_i$ 插队，排在最后一个优先级不低于自己的学生之后；
2. 同一时间返回的学生，按 $s_i$ 升序排列。

目标：求出所有学生都至少领到一次粥的最早时间。 若 $D$ 分钟内无法全员领到，输出 $-1$。

核心思路

1. 队列拆分

• 初始队列 $Q_1$：用数组保存，指针 $P$ 指向当前队首，代表还没领过第一次粥的学生。
• 回归队列 $Q_2$：用优先队列维护，按优先级降序、$s_i$ 升序排序。

2. 关键优化：后缀最大值

预处理后缀最大值数组 $sufMax$： $sufMax[P]$ 表示初始队列从 $P$ 到末尾的最大优先级。

选择规则：

• 若 $Q_2$ 队首优先级 ≤ $sufMax[P]$：优先服务初始队列 $Q_1$。
• 否则：优先服务回归队列 $Q_2$。

3. 回归事件处理

用数组 $eat$ 记录回归事件： $eat[t]$ 存储在第 $t$ 分钟结束时返回的所有学生。 每分钟结束后，将这批学生加入优先队列。

算法流程

1. 读入 $n,D$ 以及每个学生的 $k_i,s_i$。
2. 预处理后缀最大值数组 $sufMax$。
3. 初始化指针 $P=1$、答案 $ans=-1$、访问标记数组 $vis$。
4. 逐分钟模拟（从 $1$ 到 $D$）：
   • 根据后缀最大值判断，选择 $Q_1$ 或 $Q_2$ 的学生领粥。
   • 如果该学生是第一次领粥，打上标记。
   • 计算其回归时间，若不超过 $D$ 则加入对应 $eat$ 数组。
   • 处理当前分钟结束后回归的学生，加入优先队列。
   • 若 $P = n+1$（全员领过），记录当前时间并提前结束。
5. 输出答案。

公式与复杂度分析

时间复杂度：

复杂度说明

• 逐分钟遍历时间：$O(D)$
• 优先队列单次插入/弹出：$O(\log n)$
• 总体复杂度可通过 $D\le 3\times10^5$ 与 $n\le 2\times10^5$ 的限制。

空间复杂度：$O(n+D)$，用于存储学生信息、后缀数组、回归事件。