首页 > itarticle > VIJOS1450 – 包裹快递

VIJOS1450 – 包裹快递

admin 11月 12, 2020 0

一道二分答案的模板题。

先 $O(logN)$ 二分 Key ，然后 $O(N)$ 暴力判断解，总体复杂度 $O(NlogN)$ 。

不好的一点就是这个题卡 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);
}