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

· · 题解

P13374 [GCJ 2011 #2] Airport Walkways

题目概括

有一个长廊，里面设有不重叠的加速步道，给出在地面行走和奔跑的速度，以及每个步道的起止点和在上面的增益速度。可以选择奔跑或行走，但奔跑有时限，问时间最小值。

思路

可以很轻松的看出来这是一道贪心题。

那么，如何贪？

我们可以设两段路程 s 相等但基础速度分别为 v1 和 v2，且 v1 < v2。此时，如果奔跑带来的额外速度为 v3，那么两个路段可以减少的时间分别为 \frac{v3 \times s}{( v1 + v3 ) \times v1} 和 \frac{v3 \times s}{( v2 + v3 ) \times v2}，显而易见的，前者带来的收益更大，也就是说我们贪心的策略是速度小的优先。

我们只需要一个排序便可解决这个问题，接下来就是对于每个排在前面的步道尽量多地使用奔跑并用总时间减去节省的时间以得出答案。

这里还有个小细节：为了方便计算，我们可以将没有步道的部分看作一个整体，其速度就是行走的速度。

代码

#include <bits/stdc++.h>
using namespace std;

double T;
pair<double,double> a[100005];      //这里用pair数组存储{速度，长度} 

int main(){
    cin >> T;
    for (int j=1;j<=T;j++){
        double x,s,r,t,cnt=0,sum=0;
        int n;
        cin >> x >> s >> r >> t >> n;
        for (int i=1;i<=n;i++){     //读入 
            int b,e,w;
            cin >> b >> e >> w;
            a[i].first=w+s;
            a[i].second=e-b;
            cnt+=a[i].second;       //计算叠加行走速度后的速度和每段长度 
        }
        if (cnt<x){
            n++;
            a[n].first=s;
            a[n].second=x-cnt;      //剩下的没有步道的部分 
        }
        for (int i=1;i<=n;i++) sum+=a[i].second/a[i].first;     //总的时间 
        sort(a+1,a+n+1);        //排序 
        for (int i=1;i<=n;i++){
            if (t<=0) break;        //奔跑时间用完就停 
            double ti=a[i].second/(a[i].first+(r-s));       //如果使用奔跑，全程省下的时间 
            double tt=min(ti,t);        //有可能剩余的奔跑时间不够 
            sum-=tt*(r-s)/a[i].first;       //这里是一个整理完的算省出时间的公式 
            t-=tt;      //用了 
        }
        cout << "Case #" << j << ": ";
        printf("%.6lf\n", sum);     //保留精度 
    }
    return 0;
}

公式推导

上面的代码里有一个不太好想的公式，我已经标明，现在来推导一下：

首先，tt 是我们最终决定使用的奔跑时间，r 是奔跑速度，s 是行走速度，w 为步道基础速度。我们在 tt 时间内多走的路程是 (r + w) \times tt - (s + w) \times tt，化简便是 tt \times ( r - s ) 而这个路程在行走情况下的时间是 \frac{tt \times ( r - s )}{s + w}，也就是我们省出来的时间。

总结

只要能发现贪心的策略，这道题就基本没问题了，如果上面的公式看不懂可以自己试着推一下。

（如果有问题还请指正，谢谢）