P3743 kotori的设备

Part 1 无限使用

很简单，只要所有设备一秒内消耗的能量小于等于充电宝一秒内能提供的能量，就意味着能够一直充电。

Part 2 主程序

既然所有和的最大值是 $10^{10}$ 那么就把右边界定义为 $10^{10}$ 。

然后，题目要求的精度是 $10^{-4}$ ，所以当 $r$ 和 $l$ 相差小于等于 $10^{-4}$ 时结束 while 循环。

这样看似范围很大，但是二分的时间复杂度是 $O(\log n)$ ，即使是大数据也就几十而已。

Part 3 check 函数

设待验证的时间为 $x$ 则充电宝最多可以提供 $x*p$ 的能量。设 $t$ 表示在时间 $x$ 内所需充电宝能量，则如果一个设备在 $x$ 秒内消耗的能量小于原来储存的能量，就不需要使用充电宝。

反之，如果要使用充电宝，那么充电宝消耗的能量就是这个设备在 $x$ 秒内消耗的能量减去原储存能量。用 $t$ 做一个累加即可。

最后如果 $t$ 小于等于 $p$ ，就意味着这个时间是合法的。

AC code ：

#include<bits/stdc++.h>
using namespace std;
struct aksres
{
	double x,y;
}a[233333];
int n;
double p,sum,l,r,mid;
int check(double x)
{
	double s=x*p,t=0;
	for(int i=1;i<=n;i++) t+=max(0,x*a[i].x-a[i].y);
	return t<=s;
}
int main()
{
	cin>>n>>p;
	for(int i=1;i<=n;i++)
	{
		scanf("%lf%lf",&a[i].x,&a[i].y);
		sum+=a[i].x;
	}
	if(sum<=p) {cout<<"-1";return 0;}
	l=0.0;r=1e10;
	while(r-l>0.0001)
	{
		mid=(l+r)/2.0;
		if(check(mid)) l=mid;
		else r=mid;
	}
	printf("%.6lf",l);
	return 0;
}