题目传送门
题目思路
能无限使用的情况显然，就是当所有设备的能量消耗速度的总和小于等于充电宝的充电速率时，可以无限使用。这时候直接输出 −1−1 即可。
我们看到，题目要求能使用时间的最大值，而并不需要求出如何使用充电宝。这种类型的题目，我们第一个想到的就是动态规划。
但是我们会发现，动态规划并不能维护题目所要求的东西。所以我们将思路转向另一种求最值问题的方法：二分答案。
找到了这个思路以后，我们要处理的最关键的问题，就是如何在时间已经确定的情况下用 O(n) 的复杂度判断能否使用这么长时间，这也是本题最大的难点。
我们考虑一个贪心策略。
首先，如果一个设备在 t 的时间内消耗的能量小于或等于原有的能量，那么我们自然没有必要浪费时间给它充电，因为它在这段时间内的能量不会降为 0 。
然后我们考虑设备消耗的能量大于原有能量的情况。
由于我们并不在乎什么时候给设备充电，所以我们只需要对于每一个这样的设备，求出我们需要给它充的电即可。求出需要的电的方法显然，就是 ai∗t−bi 。
然后我们只需要把所有的需要充电的设备需要充的电加起来，判断充电宝能否在 t 的时间内充这么多的电即可。
同时因为有1e5个设备，每个设备最多1e5电量，上界开1e10
大陷阱：注意浮点陷阱。。因为这个导致死循环了，因为某种意义上3.0<3.0，3.0>3.0是可能都存在的。。fuck！
AC代码
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int n, p;
cin >> n >> p;
vector<double> a(n);
vector<double> b(n);
long long fsum = 0;
for (int i = 0; i < n; i++)
{
cin >> a[i];
cin >> b[i];
fsum += a[i];
}
if (fsum <= p)
{
cout << -1 << endl;
return 0;
}
double l = 0;
double r = 1e10;
double ans = 0.0;
while (1e-5 < r - l)
{
double mid = (l + r) / 2.0;
double sum = 0;
for (int i = 0; i < n; i++)
{
if (b[i] > a[i] * mid)
continue;
sum += a[i] * mid - b[i];
}
if (sum <= (double)p * mid)
{
l = mid + 0.00001;
ans = mid;
}
else
{
r = mid;
}
}
cout << ans << endl;
return 0;
}