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

CodeForce-801C Voltage Keepsake(二分)

2024-10-16 16:53:38   213人阅读

题目大意：有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(二分)


联系
我们