题解：P13374 [GCJ 2011 #2] Airport Walkways

· · 题解

题解：P13374 [GCJ 2011 #2] Airport Walkways

题目链接

思路

首先我们要思考一点，哪些路段使用奔跑能降低总时间？按照常理来说，应该就是在速度最低的时候奔跑，所以我们考虑贪心。

首先计算各路段的基础通行时间，然后考虑在这些路段上分配奔跑时间。

计算无步道路段长度，将其视为速度为 S 的特殊路段，计算所有路段以步行速度通过的总时间，将路段按从小到大排序，然后分配时间，这里就需要贪心。

先计算在该路段上完全奔跑所需时间，再计算实际奔跑时间，算一下它们节省了多少时间，再用剩余奔跑时间减去实际奔跑时间。如果剩余奔跑时间为 0，即代表用完了就结束。最后答案就是初始时间减去节省的时间。

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct data1{
    double l,v;
}s[1005];
double x,sp,r,t,sum,ans,tot,lst,num,b,e,w;
int n,ta;
bool cmp(data1 a,data1 b){return a.v<b.v;}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout<<fixed<<setprecision(6);//误差在10^6以内 
    cin>>ta;
    for(int k=1;k<=ta;k++)
    {
        cin>>x>>sp>>r>>t>>n;
        sum=0;
        for(int i=1;i<=n;i++)
        {
            cin>>b>>e>>w;
            s[i].l=e-b;
            s[i].v=sp+w;
            sum+=s[i].l;
        }
        if(x>sum)
        {
            s[++n].l=x-sum;
            s[n].v=sp;
        }
        tot=0;
        for(int i=1;i<=n;i++) tot+=s[i].l/s[i].v;
        sort(s+1,s+n+1,cmp);
        lst=t;
        num=0;
        for(int i=1;i<=n;i++)
        {
            if(lst<=0) break;
            double sp1=s[i].v+(r-sp);
            double ma=s[i].l/sp1;
            double use=min(lst,ma);
            num+=use*(r-sp)/s[i].v;
            lst-=use;
        }
        ans=tot-num;
        cout<<"Case #"<<k<<": "<<ans<<'\n';
    }
    return 0;
}