VIJOS1450 - 包裹快递

2016/11/17

一道二分答案的模板题。

二分 Key ,然后 暴力判断解,总体复杂度

不好的一点就是这个题卡 IO 和 EPS 。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <cstdio>
using namespace std;
typedef double LB;
const int MAX = 200000 + 1000;
const LB  EPS = 1E-4;
LB X[MAX], Y[MAX], S[MAX];
int N; LB P;

bool check(LB v) {
    P = 0.0;
    for(int i=1;i<=N;i++) {
        P += S[i] / v;
        if(P > Y[i]) return false;
        if(P < X[i]) P = X[i];
    }
    return true;
}

int main() {
    cin >> N;
    for(int i=1;i<=N;i++) scanf("%lf%lf%lf", &X[i], &Y[i], &S[i]);
    LB L = 0.0, R = 10000000000.0, ans = 0.0;
    while(R - L > EPS) {
        LB Mid = (L + R) / 2.0L;
        if(check(Mid)) R = Mid - EPS, ans = R;
        else L = Mid + EPS;
    }
    printf("%.2lf", ans);
}