题目背景
kotori 有 n 个可同时使用的设备。
题目描述
第 i 个设备每秒消耗ai个单位能量。能量的使用是连续的，也就是说能量不是某时刻突然消耗的，而是匀速消耗。也就是说，对于任意实数 ,在 k 秒内消耗的能量均为k*ai 单位。在开始的时候第 i 个设备里存储着bi个单位能量。
同时 kotori 又有一个可以给任意一个设备充电的充电宝，每秒可以给接通的设备充能p 个单位，充能也是连续的，不再赘述。你可以在任意时间给任意一个设备充能，从一个设备切换到另一个设备的时间忽略不计。
kotori 想把这些设备一起使用，直到其中有设备能量降为 0。所以 kotori 想知道，
在充电器的作用下，她最多能将这些设备一起使用多久。
输入格式
第一行给出两个整数 n,p。
接下来 n 行，每行表示一个设备，给出两个整数，分别是这个设备的ai 和 bi。
输出格式
如果 kotori 可以无限使用这些设备，输出-1。
否则输出 kotori 在其中一个设备能量降为 0 之前最多能使用多久。
设你的答案为 a,标准答案为 b,只有当 a,b 满足
的时候，你能得到本测试点的满分。
输入
2 1
2 2
2 1000
输出
2.0000000000
输入
1 100
1 1
输出
-1
输入
3 5
4 3
5 2
6 1
输出
0.5000000000
说明/提示
对于 100%的数据， 1<=n<=100000，1<=p<=100000，1<=ai,bi<=100000。
思路：
所有的充电和耗电都是线性的，单位时间内消耗一定的量，所以一秒钟我可以其中四分之一的时间充a1，四分之一的时间充a2…所以直接二分答案，二分总时间，check函数判断标准是看需要的总能量和可以冲的总能量的大小，可充总能量多说明这还不是极限。最后特判一下-1的情况（可以无限充，一秒内需要的总能量小于可充的能量，供大于求）即可
#include<string.h>
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<map>
#include<unordered_map>
using namespace std;
typedef long long ll;
typedef pair<double,ll>pdl;
#define debug(x) cerr<<"# "<<x<<endl
const ll N=200007;
const ll base=137;
const ll mod=2147483647;
const int INF = 1<<30;
ll n,m;
double p,a[N],b[N];
double res;
double E=1e-6;
inline bool check(double ans)
{
double sum=0;
double en=ans*p;
for(int i=1;i<=n;++i)
{
if(a[i]*ans<=b[i])
continue;
sum+=(a[i]*ans-b[i]);
}
return sum<=en;
}
int main()
{
scanf("%lld%lf",&n,&p);
double sum=0;
for(int i=1;i<=n;++i)
{
scanf("%lf %lf",&a[i],&b[i]);
sum+=a[i];
}
if(sum<=p)
{
printf("-1\n");
return 0;
}
double l=0.0,r=1e10;
while(l+E<r)
{
double mid=(l+r)/2;
if(check(mid))l=mid,res=mid;
else r=mid;
}
printf("%.10f\n",res);
return 0;
}
有任何疑问欢迎评论哦虽然我真的很菜
京公网安备 11010502036488号