题意

有 $n$ 台设备同时运行。第 $i$ 台设备每秒消耗 $a_i$ 单位能量，初始存有 $b_i$ 单位能量。一个功率为 $p$ 的充电宝可以随时在设备之间切换，切换不耗时。

求所有设备能够共同运行的最长时间；如果可以永远运行，输出 -1。

思路

先判断能否无限运行

记所有设备的总耗能率为：

如果 $A\leqslant p$，充电宝的平均供能率足以覆盖全部设备的总耗能率。由于它可以无代价地连续切换，可以按各设备的耗能率分配充电时间，因此设备能够无限运行，答案是 -1。

如果 $A>p$，系统总能量每秒至少净减少 $A-p$。初始总能量有限，所以答案一定有限。

固定时间后，只统计能量缺口

假设要让所有设备至少运行 $t$ 秒。第 $i$ 台设备在这段时间内共消耗 $a_i t$，初始能量能承担其中的 $b_i$。它至少需要充电宝补充：

所以截至 $t$ 时刻，所有设备的最小总补能需求是：

充电宝在 $t$ 秒内最多提供 $pt$ 单位能量，因此可行性判定为：

充电宝可以连续、抢占式地在设备之间切换，能量也可以提前存入设备。可以把需要补给设备 $i$ 的每一小份能量看成一个可提前完成的任务：第 $x$ 单位外部能量最迟应在 $(b_i+x)/a_i$ 时刻送达。到时刻 $s$ 为止，设备 $i$ 的这些“已到截止时间的任务”总量正是 $\max(0,a_i s-b_i)$。

按截止时间从早到晚充电。若这种策略第一次在时刻 $s$ 无法按时供能，说明此前的全部 $ps$ 供能能力都已经用于截止时间不晚于 $s$ 的需求，但这些需求仍未完成，于是必有 $R(s)>ps$。反过来，只要每个前缀都满足 $R(s)\leqslant ps$，最早截止时间优先的充电安排就不会违约。因此前缀总量条件既必要又充分。

为什么只检查终点 $t$ 就够了

仅写出 $R(t)\leqslant pt$ 还不够，还要说明更早的时刻不会先耗尽。对任意 $t>0$，把不等式两边同时除以 $t$：

随着 $t$ 增大，$b_i/t$ 单调减小，因此每一项都单调不减，$R(t)/t$ 也单调不减。

若某个时刻 $t$ 满足 $R(t)/t\leqslant p$，那么任意 $0<s\leqslant t$ 都有：

也就是 $R(s)\leqslant ps$。所以检查终点 $t$ 已经自动保证所有更早时刻的总需求也不超出供能能力。可行时间必然构成从 $0$ 开始的一段前缀区间，可以二分最大可行值。

二分右边界

初始总能量记为：

运行 $t$ 秒共消耗 $At$，初始能量与充电宝最多只能提供 $B+pt$。可行时必须有：

因为当前讨论的是 $A>p$，移项可得：

因此可以把 $B/(A-p)$ 作为二分右边界，不需要猜测一个很大的常数。右边界即使恰好可行也没有问题，因为它已经是任何答案都不能超过的全局上界。

Python 二分 60 次，C++ 二分 80 次。数据范围下右边界最多约为 $10^{10}$，Python 60 次后区间宽度小于 $10^{-8}$，远小于题目允许的 $10^{-4}$ 相对误差。

正确性说明

1. 若 $A\leqslant p$，充电宝的总功率覆盖总耗能率，通过连续分时供能可以无限运行。
2. 若 $A>p$，总能量以正的净速率减少，答案有限，并且不超过 $B/(A-p)$。
3. 对固定时刻 $t$，第 $i$ 台设备必须从充电宝获得的最少能量恰为 $\max(0,a_i t-b_i)$，所有设备的最小总需求就是 $R(t)$。
4. $R(t)/t$ 单调不减，所以终点满足 $R(t)\leqslant pt$ 时，每个更早时刻也满足对应前缀约束；反之若终点需求超过供能，则显然不可能运行到 $t$。
5. 因而 possible(t) 与真实可行性等价，且具有单调性。二分保留最大可行时间所在区间，最终得到所需精度的答案。

brute.py 按设备自然耗尽时刻 $b_i/a_i$ 排序，并用 Fraction 在每段线性函数上精确求交点。它是独立的对拍参考解，不是更适合提交的朴素算法，因此正文不重复嵌入。

Python 知识

一次读取全部整数

题目只有整数 token，换行位置不影响解析，因此可以使用：

1data = list(map(int, sys.stdin.buffer.read().split()))

这会一次读取全部输入并转换为整数列表，适合 $n\leqslant 10^5$ 的纯数字输入。

用切片和 zip 重组设备

去掉前两个数 n, p 后，输入按 a_1,b_1,a_2,b_2,... 交错排列。代码使用：

1devices = list(zip(data[2::2], data[3::2]))

第一个切片取得所有耗能率，第二个切片取得所有初始能量，zip 再把同一设备的两个值配对。

生成器只产生需要聚合的值

判定函数先按需产生每台设备的缺口，再只汇总正缺口：

1
2lacks = (use * seconds - stored for use, stored in devices)
needed = sum(lack for lack in lacks if lack > 0.0)

生成器不会额外创建一个长度为 $n$ 的缺口列表。它只能消费一次，而这里恰好只交给 sum 遍历一次。

Fraction 只用于验证

参考程序用 fractions.Fraction 精确表示 $b_i/a_i$ 和分段线性交点，避免参考答案自身带入浮点误差。正式解需要进行 $O(n)$ 的多轮判定，使用 float 更合适。

C++ 到 Python 对照

• C++ 的两个全局数组对应 Python 的 (use, stored) 元组列表。
• C++ 在判定中用普通循环并在超出供能时提前返回；Python 用生成器和 sum 表达同一个缺口总和。
• C++ 的 long long 保存整数总量；Python 整数自动扩展，不会发生固定宽度溢出。
• C++ 的 fixed << setprecision(10) 对应 Python 的 f"{left:.10f}"。

模仿清单

1. 纯整数输入且不关心换行时，用 sys.stdin.buffer.read().split()。
2. 交错数组可以用两个步长切片配合 zip 重组。
3. “先变换、再筛选、最后求和”可以用一次性生成器交给 sum。
4. 浮点正解可以用 Fraction 分段公式作为小数据独立参考，避免两个程序共享同一种误差。

相关 Python 笔记：

• /home/rainboy/mycode/hugo-blog/content/program_language/python/generator_expression.md：生成器的惰性计算、一次性消费以及与 sum 的配合。
• /home/rainboy/mycode/hugo-blog/content/program_language/python/oj_input_output_cheatsheet.md：大量纯整数 token 的读取与固定小数位输出。
• /home/rainboy/mycode/hugo-blog/content/program_language/python/math_tools.md：浮点比较和 fractions.Fraction 精确有理数。

代码

C++17 正解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-19 09:46
 * update_at: 2026-07-19 09:59
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;

int n;
long long charger_power;
long long use_rate[MAXN];
long long stored_energy[MAXN];

bool possible(double seconds) {
    double available = charger_power * seconds;
    double needed = 0.0;

    for (int i = 1; i <= n; i++) {
        double lack = use_rate[i] * seconds - stored_energy[i];
        if (lack > 0) {
            needed += lack;
            if (needed > available) return false;
        }
    }

    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> charger_power;

    long long total_use = 0;
    long long total_stored = 0;
    for (int i = 1; i <= n; i++) {
        cin >> use_rate[i] >> stored_energy[i];
        total_use += use_rate[i];
        total_stored += stored_energy[i];
    }

    if (total_use <= charger_power) {
        cout << -1 << '\n';
        return 0;
    }

    double left = 0.0;
    double right = (double)total_stored / (total_use - charger_power);

    for (int iteration = 1; iteration <= 80; iteration++) {
        double middle = (left + right) / 2;
        if (possible(middle)) {
            left = middle;
        } else {
            right = middle;
        }
    }

    cout << fixed << setprecision(10) << left << '\n';
    return 0;
}

Python 正解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26import sys


data = list(map(int, sys.stdin.buffer.read().split()))
n, power = data[:2]
devices = list(zip(data[2::2], data[3::2]))
total_use = sum(use for use, _ in devices)

if total_use <= power:
    print(-1)
else:
    def possible(seconds):
        lacks = (use * seconds - stored for use, stored in devices)
        needed = sum(lack for lack in lacks if lack > 0.0)
        return needed <= power * seconds

    left = 0.0
    right = sum(stored for _, stored in devices) / (total_use - power)
    for _ in range(60):
        middle = (left + right) / 2
        if possible(middle):
            left = middle
        else:
            right = middle

    print(f"{left:.10f}")

复杂度

设二分迭代次数为 $I$。

• 读取数据和计算总量需要 $O(n)$ 时间。
• 每次可行性判定扫描全部设备，需要 $O(n)$ 时间。
• 总时间复杂度为 $O(In)$；Python 中 $I=60$，C++ 中 $I=80$，都可以视为 $O(n)$。
• 保存 $n$ 台设备，空间复杂度为 $O(n)$。

C++ 判定在总缺口已经超过可用能量时提前退出；Python 的生成器不保存缺口列表，因此额外临时空间为 $O(1)$。

总结

连续切换不需要真的模拟。固定一个目标时间 $t$ 后，第 $i$ 台设备只贡献一个累计缺口 $\max(0,a_i t-b_i)$，把所有缺口相加并与 $pt$ 比较即可。

更关键的是，$R(t)/t$ 单调不减：终点可行会保证所有更早时刻也满足供能约束。这个单调性使可行时间形成前缀区间；再由总能量守恒给出 $B/(A-p)$ 的有限上界，就得到完整而稳定的浮点二分算法。