题解：P6933 [ICPC2017 WF] Need for Speed

__zyq_666_kpzc__ · 2024-07-19 16:52:08 · 题解

题目传送门

思路分析

根据题意，我们可以知道：比正确答案 c 大的数一定能在规定时间内走完，比正确答案 c 小的数不可能在规定时间内走完，答案 c 具有单调性。

于是，我们可以想到用二分答案解决此题，二分最后的答案 c，在合法的范围中求出最小的答案，直接输出。

注意：最后的答案是浮点数！！！

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
const double h=1e-7;
double t,ju_li[1005],su_du[1005],l=10000000,r=10000000;;
bool check(double x){
    double sum=0;
    for(int i=1;i<=n;i++)sum+=ju_li[i]*1.0/(su_du[i]+x);
    return sum>t;
}
signed main(){
    cin>>n>>t;
    for(int i=1;i<=n;i++){
        cin>>ju_li[i]>>su_du[i];
        l=min(l,su_du[i]);
    }
    l=-l;
    while(l+h<r){
        double mid=(l+r)/2;
        if(check(mid)==true)l=mid;
        else r=mid; 
    }
    printf("%.7lf",r);
    return 0;
}