Codeforces Round #409 (Div. 2) C Voltage Keepsake(二分)

时间:2022-12-19 16:28:14

题意:有n(n<=100000)个机器。。。第i个机器最开始有bi(1<=bi <= 100000)个单位的电量,机器可以储存的电量没有上限,启动后每秒消耗ai(1<=ai<=100000)个单位的电量,有一个充电器每秒可以充p(1<=p<=1e9)的电量。求保持所有机器电量不为0的情况下最多能运行多少秒。

思路:二分答案。假设机器能运行的时间是t,那么充电器就可以有t*p个剩余。用充电器剩余的电量填补要运行t秒机器额外的电量。然后按照这个check一直二分就可以了。。由于是浮点数。。所以二分的时候要注意下eqs和上界。。

Codeforces Round #409 (Div. 2) C Voltage Keepsake(二分)Codeforces Round #409 (Div. 2) C Voltage Keepsake(二分)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define eqs 0.0000001
const int maxn = 1e5 + 10;
int n;
ll a[maxn] ,b[maxn],p;
bool check(double t){
    double sav = t * p;
    double cc = 0;
    for(int i=1;i<=n;i++){
        if(a[i]*t-b[i]>=0)
        cc += (a[i]*t - b[i]);
    }
    if(cc > sav) return 0;
    return 1;
}
int main()
{
    scanf("%d",&n);
    scanf("%I64d",&p);
    double ru = 0 , chu = 0;
    ll cc = 0;
    for(int i = 1; i <= n;i++)
        scanf("%I64d%I64d",&a[i],&b[i]), ru += b[i], chu += a[i],cc+=a[i];
    if(cc <= p) return 0*printf("-1\n");
    double r = (ru)/(chu - p);
    double l = 0;
    double ans = 0;
    int cnt = 0;
    while(l + eqs <= r){
        double  m = (l+r)/2;
        if(check(m)){
            l=m+eqs;
            ans = m;
        }
        else r= m-eqs;
        cnt++;
        if(cnt >= 5000) break;
    }
    printf("%.8f\n",ans);
}
View Code