P3743 kotori的设备

实数二分题，二分+贪心check
如果存在一种使用方法使得使用时间(ge x)，那么所有小于等于x的时间t都能够满足条件。所以可以通过二分得到使用时间的最大值。
复杂度：(O(nlog(T)))

#include<iostream>
using namespace std;

const int N = 100010;

double a[N], b[N], p;
int n;

int check(double x){
    double sum = 0;
    for(int i = 0; i < n; i ++){
        if(a[i] * x > b[i]) sum += a[i] * x - b[i];
        if(sum > x * p) return 0; // 如果总耗电数大于这段时间内充电宝能提供的最大电量，说明不能一起使用x秒
    }
    
    return 1;
}

int main(){
    cin >> n >> p;
    
    for(int i = 0; i < n; i ++) cin >> a[i] >> b[i];
    
    double sum = 0;
    for(int i = 0; i < n; i ++) sum += b[i];
    if(sum <= p){
        cout << -1;
        return 0;
    }
    
    double l = 0, r = 1e10;
    
    while(r - l >= 1e-4){
        double mid = (l + r) / 2;
        if(check(mid)) l = mid;
        else r = mid;
    }
    
    cout << l << endl;
    
    return 0;
}