【题目来源】
洛谷：P3743 小鸟的设备 - 洛谷
【题目描述】
第 \(i\) 个设备每秒消耗 \(a_i\) 个单位能量。能量的使用是连续的，也就是说能量不是某时刻突然消耗的，而是匀速消耗。也就是说，对于任意实数，在 \(k\) 秒内消耗的能量均为 \(k\times a_i\) 单位。在开始的时候第 \(i\) 个设备里存储着 \(b_i\) 个单位能量。
同时 kotori 又有一个可以给任意一个设备充电的充电宝，每秒可以给接通的设备充能 \(p\) 个单位，充能也是连续的，不再赘述。你可以在任意时间给任意一个设备充能，从一个设备切换到另一个设备的时间忽略不计。
kotori 想把这些设备一起使用，直到其中有设备能量降为 \(0\)。所以 kotori 想知道，在充电器的作用下，她最多能将这些设备一起使用多久。
【输入】
第一行给出两个整数 \(n,p\)。
接下来 \(n\) 行，每行表示一个设备，给出两个整数，分别是这个设备的 \(a_i\) 和 \(b_i\)。
【输出】
如果 kotori 可以无限使用这些设备，输出 \(−1\)。
否则输出 kotori 在其中一个设备能量降为 \(0\) 之前最多能使用多久。
设你的答案为 \(a\)，标准答案为 \(b\)，只有当 \(a,b\) 满足 \(\frac{|a-b|}{max(1,b)}\le 10^{-4}\) 的时候，你能得到本测试点的满分。
【输入样例】
2 1
2 2
2 1000
【输出样例】
2.0000000000
【解题思路】
【算法标签】
《洛谷 P3743 kotori的设备》 #贪心# #二分# #Special judge#
【代码详解】
#include <bits/stdc++.h>
using namespace std;// 全局变量：
// n: 设备数量
// p: 充电器功率
// a[100005]: 每个设备的能量消耗速率
// b[100005]: 每个设备的初始能量
// s: 所有设备的总能量消耗速率
// l, r, mid: 二分查找的左右边界和中间值
int n, p, a[100005], b[100005];
double s = 0, l, r, mid;int main()
{// 输入设备数量和充电器功率cin >> n >> p;// 输入每个设备的能量消耗速率和初始能量，并计算总消耗速率for (int i = 1; i <= n; i++){cin >> a[i] >> b[i];s += a[i];}// 检查是否可以无限使用（总消耗 <= 充电功率）if (s <= p){cout << -1 << endl;return 0;}// 初始化二分查找边界l = 0; // 最小可能时间为0r = 1e10; // 设置一个足够大的上界// 二分查找最大可使用时间while (l <= r){mid = l + (r - l) / 2; // 计算中间时间值// 当左右边界足够接近时终止循环if (r - l < 0.00001){break;}double sum = 0; // 需要补充的总能量// 计算所有设备在当前时间下需要补充的能量for (int i = 1; i <= n; i++){if (b[i] < mid * a[i]) // 如果初始能量不足{sum += mid * a[i] - b[i]; // 计算需要补充的能量}}// 判断充电器能否在mid时间内提供足够的能量if (sum <= p * mid) // 可以满足，尝试更长时间{l = mid;}else // 不能满足，尝试更短时间{r = mid;}}// 输出最大可使用时间（保留10位小数）printf("%.10lf", l);return 0;
}
【运行结果】
2 1
2 2
2 1000
1.9999996104