洛谷题单指南-二分查找与二分答案-P3743 kotori的设备

原题链接：https://www.luogu.com.cn/problem/P3743

题意解读：设备使用的时间越久，需要充电的总时间也越多，具备单调性，根据使用的时间，计算需要充电的时间，如果充电总时间<=使用的时间，说明有电量还能富余，使用时间还可以更多，因此只需对使用时间进行二分即可。

解题思路：

给定设备使用的时间x，要计算充电总时间，

需要计算每一个设备要使用x秒，需要充电多久，累加充电时间即可

如果充电总时间<=x，继续往大的方向二分，如果充电总时间>x，继续往小的方向二分。

有两个点要注意：

1、二分的精度是10⁻⁴，所以在判断r - l时加两位r - l > 10^-6

2、所有设备总能量不超过10⁵*10⁵=10¹⁰，二分的最大值设置为10¹⁰，如得到的结果大于等于最大值，则认为可以无限使用，输出-1

100分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 100005;
const double MAXX = 1e10;

struct device
{
    double a, b;
} d[N];

int n;
double p, ans;

bool check(double x)
{
    double all = 0; //需要充电的总时间
    for(int i = 1; i <= n; i++)
    {
        if(d[i].b < d[i].a * x) //如果电不够，才充电
            all += (d[i].a * x - d[i].b) / p;
    }
    return all <= x;
}

int main()
{
    cin >> n >> p;
    for(int i = 1; i <= n; i++) 
    {
        cin >> d[i].a >> d[i].b;
    }
    double l = 0, r = MAXX;
    while(r - l > 1e-6)
    {
        double mid = (l + r) / 2;
        if(check(mid)) ans = mid, l = mid;
        else r = mid;
    }
    if(ans >= MAXX) ans = -1;
    cout << ans;

    return 0;
}