首页 > 代码库 > CodeForce-801C Voltage Keepsake(二分)

CodeForce-801C Voltage Keepsake(二分)

题目大意:有n个装备,每个设备耗能为每单位时间耗能ai,初始能量为bi;你有一个充电宝,每单位时间可以冲p能量,你可以在任意时间任意拔冲。

如果可以所有设备都可以一直工作下去,输出-1;否则,输出所有设备都同时工作的最长时间。

思路提示:想象这样一个场景,每当一个设备没电时,你就拔掉你正在充电的设备,冲到这个设备上。可是,天有不测风云,突然某一刻,有2个以上设备同时没电,那至少有一个设备得停止工作。这一刻也就是答案,让我们来看一看这一刻的状况,设这一刻为t,充电宝总共供能t*p,这时t*p==sum(a[i]*t)-sum(b[i]);当t*p<sum(a[i]*t)-sum(b[i])说明t比答案大;当t*p>sum(a[i]*t)-sum(b[i])说明,t比答案小。

方法:在实数域上二分,不断逼近答案。

#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
const int N=1e5+5;
const double eps=1e-4;//精度
int n,p;
int a[N],b[N];
int check(double mid)
{
    double E=mid*p; 
    for(int i=0;i<n;i++)
    {
        double e=b[i]-a[i]*mid;
        if(e<0)E+=e;
        if(E<0)return 0;//如果充电宝的能量不足以供应,说明mid太大
    }
    return 1;//否则mid太小
}
int main()
{
    cin>>n>>p;
    ll sum=0;
    for(int i=0;i<n;i++)
    {
        cin>>a[i]>>b[i];
        sum+=a[i];
    }
    if(sum<=p)
    {
        cout<<-1<<endl;
        return 0;
    }
    double low=0,high=1e18;
    double mid;
    while(high-low>=eps)//实数域上的二分不可能为0,只能以精度控制
    {
        mid=(high+low)/2;
        if(check(mid))low=mid;
        else high=mid;
    } 
    cout<<mid<<endl;
    return 0;
}

 

CodeForce-801C Voltage Keepsake(二分)