题解 P3743 【kotori的设备】

· · 题解

本题可以使用二分答案的解法。

对于二分答案，就是利用二分算法来找到答案，如果当前答案可行，则最终的答案一定大于等于它，否则最终的答案小于等于它。

二分部分代码：

    l=0.0;
    r=3000000001.0;//如果定1e9,会发现有一个测试点过不了，因为答案大于1e9。
    while(l<=r-1e-6)//题目中误差不得大于1e-4,这里我定1e-6可以免得卡精度。
    {
        mid=(l+r)/2;
        if(check(mid))//判断答案是否可行。

        {
            l=mid;
        }
        else {
            r=mid;
        }//二分答案。
    }
    printf("%lf",r);

我们还需要一个check()函数，判断当前的答案是否可行。


int check(double m)
{
    double c=0;
    for(int i=1;i<=n;i++)
    {
        if(a[i]*m>b[i])
        c+=(a[i]*m-b[i]);//如果设备原有电量不够用，那么必须充电。
    }
    c-=p*m;
    if(c>0.0)return 0;
    return 1;
    //最后判断要充的电量是否小于等于可充的电量，是则返回真，否则为假。
}

还有一个特判：如果所有设备单位时间的用电量小于等于充电器单位时间的充电量，则可以无限使用，输出-1。

 double c=0;
    for(int i=1;i<=n;i++) c+=a[i];
    if(c-p<=0.0){
        printf("-1");
        return 0;
    }

完整代码：

#include<bits/stdc++.h>
using namespace std;
int n;
double p;//我定double，防止卡精度。
double a[100001],b[100001];
double l,r,mid;
int check(double m)
{
    double c=0;
    for(int i=1;i<=n;i++)
    {
        if(a[i]*m>b[i])
        c+=(a[i]*m-b[i]);//如果设备原有电量不够用，那么必须充电。
    }
    c-=p*m;
    if(c>0.0)return 0;
    return 1;
    //最后判断要充的电量是否小于等于可充的电量，是则返回真，否则为假。
}
int main()
{
    scanf("%d%lf",&n,&p);
    for(int i=1;i<=n;i++)scanf("%lf%lf",&a[i],&b[i]);
    double c=0;
    for(int i=1;i<=n;i++) c+=a[i];
    if(c-p<=0.0){
        printf("-1");
        return 0;
    }
     l=0.0;
    r=3000000001.0;//如果定1e9,会发现有一个测试点过不了，因为答案大于1e9。
    while(l<=r-1e-6)//题目中误差不得大于1e-4,这里我定1e-6可以免得卡精度。
    {
        mid=(l+r)/2;
        if(check(mid))//判断答案是否可行。

        {
            l=mid;
        }
        else {
            r=mid;
        }//二分答案。
    }
    printf("%lf",r);
}