题解：P6912 [ICPC2015 WF] Ship Traffic

Adolfo_North · 2024-09-09 22:06:05 · 题解

这翻译，多读几遍勉强看的懂吧。但题目是真心不难。

我们考虑对于每一艘船，计算渡轮可以通过的时间区间并记录，然后暴力的去计算每两艘船，或者自己和自己可以允许渡轮可以通过的时间段，取最大值即可。

具体看代码（无需多言了吧）：

#include<bits/stdc++.h>
using namespace std;
int n;
double w,u,v,t1,t2;
struct node{
    double l;
    int val;
};
vector<node> G;
bool cmp(node x,node y){
    if(x.l==y.l) return x.val<y.val;
    return x.l<y.l;
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>w>>u>>v>>t1>>t2;
    G.push_back({t1,0});
    G.push_back({t2,0});
    for(int i=1,m,dop;i<=n;i++){
        char op;
        cin>>op>>m;
        if(op=='W') dop=1;
        else dop=-1;
        while(m--){
            double l,p;
            cin>>l>>p;
            double st=max(t1,dop*p/u-w*i/v),en=min(t2,(dop*p+l)/u-w*(i-1)/v);
            if(st>=t2||en<=t1) continue;
            G.push_back({st,1});
            G.push_back({en,-1});
        }
    }
    sort(G.begin(),G.end(),cmp);
    double ans=-1,fl=0;
    for(size_t i=0;i<G.size()-1;i++){
        fl+=G[i].val;
        if(!fl) ans=max(ans,G[i+1].l-G[i].l);
    }
    cout<<fixed<<setprecision(8)<<ans;
    return 0;
}