OneCoder Avatar
OneCodercoderli.com · 1022 篇博文
五级

C++ 算法考级专栏

🎨 视觉封面

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

📅 2026-08-17·✍️ OneCoder·计算中...·⏱️ 12 分钟

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

luogu-P3743 小鸟的设备

题目要求

题目描述

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

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

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

输入格式

第一行给出两个整数 。

接下来 行,每行表示一个设备,给出两个整数,分别是这个设备的 和 。

输出格式

如果小鸟可以无限使用这些设备,输出 。

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

设你的答案为 ,标准答案为 ,只有当 满足 的时候,你能得到本测试点的满分。

输入输出样例 #1

输入 #1
PLAINTEXT3 行
2 1
2 2
2 1000
输出 #1
PLAINTEXT1 行
2.0000000000

输入输出样例 #2

输入 #2
PLAINTEXT2 行
1 100
1 1
输出 #2
PLAINTEXT1 行
-1

输入输出样例 #3

输入 #3
PLAINTEXT4 行
3 5
4 3
5 2
6 1
输出 #3
PLAINTEXT1 行
0.5000000000

说明/提示

对于 的数据,,,。


题目分析

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

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

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

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

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

对于目标运行时间 :

  • 第 个设备在时间 内的总消耗能量为:。
  • 第 个设备自身自带的初始电量为:。
  • 如果 :该设备自身初始能量充足,在时间 内不需要任何外部充能。
  • 如果 :该设备自身能量不足,产生的能量缺口为 。必须由充电宝为其补足这部分能量。
  • 因此,所有设备在时间 内产生的总能量缺口为:
  • 在时间 内,功率为 的充电宝最多能提供的总能量为:

核心结论:当且仅当 时,时间 是可行的。

2. 特判无穷解情况(-1)

所有设备每秒消耗的总能量速率为 。充电宝每秒提供的总充能量为 。

如果充电宝的供能速率大于等于所有设备的总消耗速率,即: 此时即使所有设备的初始电量 全部为 ,充电宝也足以支撑所有设备的持续运转。因此可以无限使用,直接输出 -1。

3. 单调性与实数二分

  • 如果所有设备可以一起运行 秒,那么显然也可以运行任意 秒;
  • 如果无法坚持 秒,那么对于任意 秒也必然无法坚持。

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

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

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

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

示例代码

C++68 行
#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;
}

复杂度分析与总结

阶段 计算操作 时间复杂度 空间复杂度 说明
输入与特判 累加 并与 比较 一次遍历
实数二分查找 迭代 100 次,每次调用 check 单次 check 耗时
总体评估 整体执行 在 时运算量约 次,耗时约 ,轻松 AC

总结:

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

所有代码开源上传至 GitHub:yummy-code 仓库 · GESP 专题站:GESP WIKI

🤝 技术交流与答疑

欢迎加入:C++ GESP/CSP 考级答疑群(688906745) 与 Java/Python交流群(982860385),点击可直接加群。

📚

猜你想读 · 相关文章推荐

OneCoder

OneCoder

一个中年人的自留地,记录学习 C++、GESP/NOI、Java、Python 与算法架构的心得体会。本站唯一网址:coderli.com

读者讨论与留言

共 0 条讨论
邮箱必填 · 支持 Markdown 格式与直接回复
💬 还没有读者留言,快来成为第一个讨论者吧!