# 题解：共用充电器

贡献：出题人解法提供二分、截止时间计数，以及优先队列模拟。Codex（GPT-6）补全证明，修复可行性边界和总量溢出，整理实现，并提供单调桶模拟与验证。

## 固定功率后的充电任务

初始电量已满足 $a_i\ge mb_i$ 的设备无需充电，直接去除，其中包括所有 $b_i=0$ 的设备。

固定功率 $X$ .设备 $i$ 第 $j$ 次充电前，已获得的总能量是 $E=a_i+(j-1)X$ .若 $E\ge mb_i$ ，不再需要充电；否则它的下一次充电最晚必须安排在分钟

$$d=\left\lfloor E/b_i\right\rfloor.$$

因为到该分钟末，累计消耗为 $(d+1)b_i>E$ ；更早的分钟末尚可承受。把这次充电看成一个占用一分钟、截止时间为 $d$ 的任务。所有任务都可提前安排，没有电池容量限制。

## 截止时间前缀条件

设 `Deadlines[d]` 是截止时间恰好为 $d$ 的任务数。可行的充要条件为：对每个 $t=0,\ldots,m-1$ ，

$$\sum_{d=0}^{t}\mathrm{Deadlines}[d]\le t+1.$$

必要性来自可用的分钟数。充分性：按截止时间非递减顺序执行任务。若某任务排在位置 $s$ 却有截止时间 $d<s$ ，则截止时间至多 $d$ 的任务超过 $d+1$ 个，与条件矛盾。同一设备各次充电的截止时间非递减，平局时按充电次数顺序安排，因此不会破坏设备内的先后关系。

枚举各设备的必要充电任务。任务总数超过 $m$ 立即失败，故一次判定最多生成 $m+1$ 个任务，再检查前缀和。$X=0$ 且仍有缺电设备时，也会通过这一上限终止。判定总计 $O(n+m)$ .

## 二分和整数安全

取

$$H=\max_i\max(0,mb_i-a_i).$$

若任何功率能成功，功率 $H$ 也能成功：每台缺电设备只需在其首次断电前充一次，其后能量足以支持整场。更大功率也不能推迟第一次必须充电的时刻。因此先单独检验 $H$ ，失败则输出 $-1$ ；成功后在 $[0,H]$ 内二分。提高功率不会破坏可行性。

即使上下界相等，也必须进行可行性判定。例如两台设备都以零电量开始、每分钟耗电1、考试2分钟时，两台都需要在第0分钟充电，无解。

所有单台能量用64位有符号整数。$H\le5\cdot10^{14}$ ；累加到达到目标就停止，因此不会溢出。不要把所有设备的总缺电量累加到64位变量，其最大值可超过该范围。

## 复杂度与方案选择

设 $n$ 为设备数，$m$ 为分钟数，$H$ 为上述上界。时间为 $O((n+m)(1+\log(H+1)))$ ，空间 $O(n+m)$ .[std.cpp](std.cpp) 使用截止时间统计作为首选。

出题人的另一思路是每分钟从最小堆取出下一次截止时间最早的设备，充电后更新其截止时间，单次判定 $O(n+m\log(n+1))$ .交换执行顺序可把任意可行安排改为此贪心安排，故同样正确。[单调桶方案](solution-alternative.zh.md) 利用截止时间是 $0$ 到 $m-1$ 的整数，进一步把模拟降至 $O(n+m)$ ；它保留逐分钟选择设备的过程，便于恢复具体安排，正式数据结果正确，但最慢中位数约0.738秒超过0.5秒时限，作为需要恢复执行顺序时的备用方案。

## 性能

正式数据每份运行五次并另测峰值。标准程序最慢中位数 0.226576 秒，峰值 19.33 MiB；按2倍取整到0.5秒，时限为 0.5 秒。补充程序最慢中位数 0.737621 秒，峰值 25.43 MiB。 [环境说明](../../../docs/评测环境与性能.md)与[逐次测量](../../../docs/benchmark-R34.json)可供复现；其他环境需重新校准。