题解：P13165 [GCJ 2017 #1B] Steed 2: Cruise Control

· · 题解

题目大意

一共有 T 组数据，每组数据有两个整数 D 和 N。N 代表马的数量。之后给出 N 条马目前所处的位置和它的速度，问 Annie 的马在不超过其他马的前提下，最大速度是多少。

思路分析

题目中说 Annie 和其他 N 匹马都沿着一条单向公路向东行进。我们可以把这条单项公路看作一个数轴，Annie 最开始时位于数轴的起点，也就是 0 位置。输入的 D 表示所有马的目的地，也就是 Annie 的终点。题目中说所有马都不会超过它前面那条马，如果追上了就会将自己的速度减至更慢的那匹马的速度。所以 Annie 既然不想超过其他的马，就一定会受最慢的那匹马的限制，那我们就需要找出最慢的那匹马的速度。这匹马既然速度最慢，那如果没有不能超过其他马的限制，它所花费的时间肯定是最多的。所以我们可以求出本来每匹马所需要花费的时间，找到最大值，最后用总路程除以时间即可。

代码实现

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
double T,d,n,k[N],s[N],t[N], maxn;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    std::cin>>T;
    for(int i=1;i<=T;i++){
        std::cin>>d>>n;
        maxn=-100;
        memset(t,0,sizeof(t));//多测不清空，爆零两行泪 
        for(int j=1;j<=n;j++){
            std::cin>>k[j]>>s[j];
            t[j]=(d-k[j])/s[j];//求出花费的时间 
            maxn=max(maxn,t[j]);//找最大值 
        }
        std::cout<<"Case #"<<i<<": ";
        std::cout << fixed <<setprecision(6) << double(d)/maxn <<"\n";//求出速度 
    }
        return 0;
}