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

· · 题解

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

题意

Annie 骑着马沿着一条单向公路行进。她位于公路的 0 处，目的地在 D 处，还有 N 匹其他马同样行进，它们都会一直前进下去，目前都位于 Annie 的马和她的目的地之间。Annie 不想追上其他的马，请问她能选择的最大速度是多少？

思路

我们不需要考虑一条马追上另一条马，速度可能会改变这一条件，因为追上另一匹马的马，所用的时间肯定与追上的那匹马是时间相等，我们只要统计出所有马到 D 点的距离，从中取出一个最大值，就是 Annie 的马行驶的最快时间，此时间内 Annie 的马总共行驶了 D 公里，用 D 除以最快时间就是答案。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int t,op=0;
signed main()
{
    cin>>t;
    while(t--)
    {
        op++;
        double d;
        int n;
        cin>>d>>n;
        double ans=0;
        for(int i=1;i<=n;i++)
        {
            double x,y;
            cin>>x>>y;
            double tim=(d-x)/y;
            ans=max(ans,tim);
        }
        printf("Case #%d: %10lf\n",op,d/ans); 
    }
    return 0;
}