P9784 [ROIR 2020 Day1] 超速 题解

· · 题解

题目意思

有 n 条道路，每段公路的长度 l_i，限速是 v_i，超速就要按照规定罚款，不同的超速程度有不同金额的罚款，每一辆车从 s_i 的时刻开始行驶，t_i 的时刻离开该条公路，求最小的最大罚款金额。

思路

题目中说最小的最大罚款金额，我们可以考虑二分枚举限速范围，时间复杂度 O(qn \log m)。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i, l, r) for(int i = l; i <= r; ++ i)
#define per(i, r, l) for(int i = r; i >= l; -- i)
const int N = 1e5 + 10;
int l[N], v[N], a[N], f[N], n, m, Q, s, t;
double d[N];
main()
{
    scanf("%lld", &n);
    rep(i, 1, n) scanf("%lld", &v[i]);
    rep(i, 1, n) scanf("%lld", &l[i]);
    scanf("%lld", &m);
    rep(i, 1, m - 1) scanf("%lld", &a[i]);
    rep(i, 1, m) scanf("%lld", &f[i]);
    rep(i, 0, m - 1) rep(j, 1, n) d[i] += 1.0 * l[j] / (v[j] + a[i]);
    scanf("%lld", &Q);
    for(; Q; -- Q)
    {
        scanf("%lld %lld", &s, &t);
        int l = 0, r = m + 1;
        for(; l <= r;)
        {
            int mid = (l + r) >> 1;
            if(d[mid] <= t - s) r = mid - 1;
            else l = mid + 1;
        }
        printf("%lld\n", f[l]);
    }
    return 0;
}