P9784 ROIR 2020 Day1 超速 题解

MA_tian · 2024-03-21 20:55:32 · 题解

这题测试点是真的多

题目大意

有 n 条道路，第 i 公路长 l_i 米，限速为 v_i 米，超速就要按照给定规则分段罚款，每辆车从 s_i 时刻开始行驶，v_i时刻离开公路。求最小的最大罚款金额。

思路

最小的最大，一眼二分答案。

不知道二分的建议先搞懂这题。

这题与二分模版不同的是，你需要先计算经过公路的时间，然后再对罚款范围进行二分。

代码

代码中的变量名意义与题目相同。

#include<bits/stdc++.h>
using namespace std;
int n,m,q,s,t,v[100005],l[100005],a[100005],f[100005];
bool check(int p){
    double use=0;//利用double变量保留精度
    for(int i=1;i<=n;i++){
        use+=l[i]/(v[i]+p);
    }
    return use+s<=t;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>v[i];
    }
    for(int i=1;i<=n;i++){
        cin>>l[i];
    }
    cin>>m;
    for(int i=1;i<m;i++){
        cin>>a[i];
    }
    for(int i=1;i<=m;i++){
        cin>>f[i];
    }
    cin>>q;
    while(q--){
        int l=0,r=m-1,mid;
        cin>>s>>t;
        while(l<r){
            mid=l+(r-l)/2;
            if(check(a[mid])){
                r=mid;
            }else{
                l=mid+1;
            }
        }
        if(!check(a[l])){
            l++;
        }
        cout<<f[l]<<endl;
    }
    return 0;
}

此题完结撒花！

夹带点私货

满堂花醉三千客，一剑霜寒十四州。