【GESP】C++五级练习 luogu-P3743 小鸟的设备

GESP C++五级练习，实数二分答案与数学建模经典题目。考察在连续充能与消耗模型下，如何利用全局能量守恒将微观调度转化为宏观供需判定，并通过实数二分搜索最大可行时间。难度⭐⭐⭐。洛谷难度等级普及+/提高。

luogu-P3743 小鸟的设备

题目要求

题目描述

小鸟有 $n$ 个可同时使用的设备，第 $i$ 个设备每秒消耗 $a_i$ 个单位能量。能量的使用是连续的，也就是说能量不是某时刻突然消耗的，而是匀速消耗。也就是说，对于任意实数，在 $k$ 秒内消耗的能量均为 $k\times a_i$ 单位。在开始的时候第 $i$ 个设备里存储着 $b_i$ 个单位能量。

同时小鸟又有一个可以给任意一个设备充电的充电宝，每秒可以给接通的设备充能 $p$ 个单位，充能也是连续的，不再赘述。你可以在任意时间给任意一个设备充能，从一个设备切换到另一个设备的时间忽略不计。

小鸟想把这些设备一起使用，直到其中有设备能量降为 $0$。所以小鸟想知道，在充电器的作用下，她最多能将这些设备一起使用多久。

输入格式

第一行给出两个整数 $n,p$。

接下来 $n$ 行，每行表示一个设备，给出两个整数，分别是这个设备的 $a_i$ 和 $b_i$。

输出格式

如果小鸟可以无限使用这些设备，输出 $-1$。

否则输出小鸟在其中一个设备能量降为 $0$ 之前最多能使用多久。

设你的答案为 $a$，标准答案为 $b$，只有当 $a,b$ 满足 $\dfrac{|a-b|}{\max(1,b)} \leq 10^{-4}$ 的时候，你能得到本测试点的满分。

输入输出样例 #1

输入 #1

2 1
2 2
2 1000

输出 #1

2.0000000000

输入输出样例 #2

输入 #2

1 100
1 1

输出 #2

-1

输入输出样例 #3

输入 #3

3 5
4 3
5 2
6 1

输出 #3

0.5000000000

说明/提示

对于 $100\%$ 的数据，$1\leq n\leq 10^5$，$1\leq p\leq 10^5$，$1\leq a_i,b_i\leq 10^5$。

题目分析

本题属于经典的 实数二分答案（Binary Search on Answer） 与 全局能量守恒建模 问题。

1. 问题本质与模型转化（宏观守恒 vs 微观调度）

初读题目时，容易陷入“每秒或每毫秒应该把充电器插在哪个设备上”的微观时间调度思维。但题目给出了两个关键约束：

1. 能量消耗与充能是连续的（匀速流动）；
2. 充电宝在不同设备间的切换时间忽略不计。

这意味着在一段连续时间 $T$ 内，充电宝可以任意切分时间片分别充给需要的设备。我们无需关心具体某一微秒在给谁充电，只需从全局能量供需平衡的角度来考察：

对于目标运行时间 $T$：

• 第 $i$ 个设备在时间 $T$ 内的总消耗能量为：$E_{\text{consume}} = a_i \cdot T$。
• 第 $i$ 个设备自身自带的初始电量为：$b_i$。
• 如果 $b_i \ge a_i \cdot T$：该设备自身初始能量充足，在时间 $T$ 内不需要任何外部充能。
• 如果 $b_i < a_i \cdot T$：该设备自身能量不足，产生的能量缺口为 $a_i \cdot T - b_i$。必须由充电宝为其补足这部分能量。
• 因此，所有设备在时间 $T$ 内产生的总能量缺口为： $E_{\text{need}}(T) = \sum_{i=1}^n \max(0.0,\ a_i \cdot T - b_i)$
• 在时间 $T$ 内，功率为 $p$ 的充电宝最多能提供的总能量为： $E_{\text{provide}}(T) = p \cdot T$

核心结论：当且仅当 $E_{\text{need}}(T) \le E_{\text{provide}}(T)$ 时，时间 $T$ 是可行的。

2. 特判无穷解情况（-1）

所有设备每秒消耗的总能量速率为 $\sum_{i=1}^n a_i$。充电宝每秒提供的总充能量为 $p$。

如果充电宝的供能速率大于等于所有设备的总消耗速率，即： $\sum_{i=1}^n a_i \le p$ 此时即使所有设备的初始电量 $b_i$ 全部为 $0$，充电宝也足以支撑所有设备的持续运转。因此可以无限使用，直接输出 -1。

3. 单调性与实数二分

• 如果所有设备可以一起运行 $T_1$ 秒，那么显然也可以运行任意 $T_0 < T_1$ 秒；
• 如果无法坚持 $T_2$ 秒，那么对于任意 $T_3 > T_2$ 秒也必然无法坚持。

由于可行性关于时间 $T$ 具有严格的单调性，因此我们可以使用二分答案来求解最大运行时间 $T$。

4. 实数二分实现细节与避坑指南

与整数二分不同，实数二分在实现时有以下几个关键考点：

1. 终止条件的选择（固定循环次数 vs eps 迭代）：
   • 常见的 while (right - left > eps) 在浮点数极端接近或上下界跨度极大时，可能由于浮点精度损失导致步长无法缩小，进而陷入死循环或 TLE。
   • 强烈推荐采用固定迭代次数（例如 for (int iter = 0; iter < 100; iter++)）。迭代 100 次可以将搜索区间缩小 $2^{-100} \approx 7.88 \times 10^{-31}$ 倍，精度远远超出题目要求的 $10^{-4}$，既安全又高效。
2. 二分上界的设定：
   • 当 $a_i, b_i \le 10^5, n \le 10^5$ 时，最大时间可能达到 $10^{10} \sim 10^{11}$ 量级。
   • 将右边界设为 1e11 是非常安全且宽松的。由于二分是每次折半，即使上界设到 $10^{11}$，100 次迭代后精度依然在 $10^{-19}$ 以下。
3. 数据类型：
   • 所有能量计算和时间变量使用 double 即可满足精度要求。

示例代码

#include <iomanip>
#include <iostream>
#include <vector>

using namespace std;

const int MAXN = 100005;

int n;
double p;
double a[MAXN], b[MAXN];

/**
 * @brief 检验在时间 T 内是否能够保证所有设备电量都不降为 0
 * @param T 目标运行时间（秒）
 * @return true 能量充足，可以坚持 T 秒
 * @return false 能量缺口过大，无法坚持 T 秒
 */
bool check(double T) {
    double total_need = 0.0;
    for (int i = 1; i <= n; i++) {
        // 如果自身初始能量不足以维持 T 秒的消耗
        if (a[i] * T > b[i]) {
            total_need += (a[i] * T - b[i]); // 累加该设备的能量缺口
        }
    }
    // 充电宝在 T 秒内最多能提供 p * T 的能量
    return total_need <= p * T;
}

int main() {
    // 优化标准 I/O 效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    if (!(cin >> n >> p)) return 0;

    double sum_a = 0.0; // 记录所有设备每秒总消耗能量速率
    for (int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i];
        sum_a += a[i];
    }

    // 1. 特判：充电功率大于等于总消耗速率，能够无限期使用
    if (sum_a <= p) {
        cout << -1 << "\n";
        return 0;
    }

    // 2. 实数二分答案
    double left = 0.0;
    double right = 1e11; // 设定一个足够大的二分上界

    // 固定迭代 100 次，区间缩小 2^(-100)，完全满足精度要求且杜绝死循环
    for (int iter = 0; iter < 100; iter++) {
        double mid = left + (right - left) / 2.0;
        if (check(mid)) {
            left = mid; // mid 秒可行，尝试寻找更大的时间
        } else {
            right = mid; // mid 秒不可行，缩小时间范围
        }
    }

    // 3. 高精度输出结果（保留 10 位小数以保证远低于 1e-4 的相对/绝对误差）
    cout << fixed << setprecision(10) << left << "\n";

    return 0;
}

复杂度分析与总结

总结：

1. 模型转化能力：遇到“连续流体”、“瞬时无损切换”类问题时，不必拘泥于时间轴上的先后顺序调度，转换为全局供需守恒是解题的核心突破口。
2. 实数二分技巧：在竞赛与等级考试中，实数二分推荐使用 for 循环固定迭代 80~100 次，相比 while (r - l > eps) 更加稳健，避免因浮点下溢造成死循环或精度不足。