Codeforces Round #409 C. Voltage Keepsake（二分+思维）

题目链接：http://codeforces.com/contest/801/problem/C

题意：给出一个充电器每秒钟充p个点，还有n个电器要同时使用a[i]表示第i个电器每秒钟用多少点，b[i]表示第i个

原来存了都少电。充电器可以无缝切换这充电，但是只能给一个充（同一时间）。最后问你最长可用多久，如果可以

无限时间的用的话，就输出-1。

题解：首先确定一下什么时候输出-1也就是可以无限充电的情况，就是p大于所有a的总和就行。

然后就是时间有限的情况。这里明确一个式子。

need*t=a[i]*t-b[i]，（need表示每秒需要的时间，t表示时间）然后for一下1～n

need+=(a[i]-b[i]/t)

如果need<=p那么这个时间就是符合的。

然后就是枚举时间，枚举时间可以用二分，不妨设l=0,r=1e10,mid=(l+r)/2。然后就是二分的次数，由于精度要求是

1e-4所以二分50次左右就够了。

#include <iostream>

#include <cstring>

#include <cstdio>

using namespace std;

const int M = 1e5 + 10;

double a[M] , b[M];

int main() {

    int n;

    double p;

    scanf("%d%lf" , &n , &p);

    double sum = 0;

    for(int i = 0 ; i < n ; i++) {

        scanf("%lf%lf" , &a[i] , &b[i]);

        sum += a[i];

    }

    if(sum <= p) {

        cout << -1 << endl;

    }

    else {

        double l = 0 , r = 1e10;

        double mid = (l + r) / 2;

        for(int j = 1 ; j <= 50 ; j++) {

            mid = (l + r) / 2;

            double need = 0;

            for(int i = 0 ; i < n ; i++) {

                need += max(0.0 , 1.0 * a[i] - b[i] / mid);

            }

            if(need <= p) l = mid;

            else r = mid;

        }

        printf("%.10lf\n" , l);

    }

    return 0;

}

巴特西

Codeforces Round #409 C. Voltage Keepsake（二分+思维）

最新文章

热门文章