题解：CF772A Voltage Keepsake

cyntmeay · 2025-09-05 14:46:47 · 题解

题目的意思很好理解，在这里不做说明。

二分答案

如果需要使用二分答案，必须要满足单调性。

如果 t 的时间满足题目的条件，那么小于 t 的时间一定满足，这就满足了单调性。

• 二分范围：因为时间不能是负数所以将左边界设为 0，右边界设置为很大的值，因为是时间越来越小才能更加满足条件。

• 判断是否满足条件：二分过程中对 mid 判断是否合法。遍历每个设备，若某一个设备在 mid 时间消耗能量大于初始能量，接下来计算出充电宝需补充的能量并求和，最后对比充电宝提供能量与总补充能量需求。

输出答案

如果 mid 满足条件则记录 mid 在二分后输出，如果答案是很大的值那就说明一直满足，可以无限使用，输出 -1。

给出代码

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,p;
int a[N],b[N];
double l,r=1e10;
bool check(double z){//判断z是否合法
    double s=0;
    for(int i=1; i<=n; i++){
        if(a[i]*z>b[i]){
            s+=a[i]*z-b[i];
        }
    }
    return p*z>=s;
}
int main() {
    scanf("%d%d",&n,&p);
    for(int i=1; i<=n; i++){
        scanf("%d%d",&a[i],&b[i]);
    }
    while(r-l>=0.0000001){
        double mid=(l+r)/2;
        if(check(mid)==true){//此时的mid合法
            l=mid;
        }
        else{
            r=mid;
        }
    }
    if(r==1e10){
        printf("-1\n");//可以无限使用
    } else {
        cout << r;
    }
    return 0;
}