Luogu

算法

二分车速,判断即可。

注意精度。

代码

#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;
typedef long double ldb;
const int N=200000+5;
const ldb EPS=1e-9;
ldb x[N],y[N],s[N];
int n;
inline bool check(ldb mid) {
    ldb nowt=0.0;
    for (re int i=1;i<=n;i++) {
        nowt=nowt+s[i]/mid;
        if (nowt<=y[i]) nowt=max(nowt,x[i]);
        else return false;
    }
    return true;
}
int main() {
    scanf("%d",&n);
    ldb L=0,R=2000000000;
    for (re int i=1;i<=n;i++)
        scanf("%llf%llf%llf",&x[i],&y[i],&s[i]);
    while (L<R-EPS) {
        ldb mid=(L+R)/2.0;
        if (check(mid)) R=mid;
        else L=mid;
    }
    cout<<fixed<<setprecision(2)<<L;
    return 0;
}
最后修改:2019 年 09 月 24 日 12 : 56 PM