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

· · 题解

看题

A 一串字母这人要骑马从 0 公里跑到 D 公里，她前面还有很多速度不一的马，A 一串字母必须匀速到达终点，不能超过任何一匹前方的马。

怎么保证不会超过呢？我们要让 A 一串字母到达终点的时间 ≥ 前面的所有马到达终点的时间中的最大值。

如果 A 一串字母比其它马提前到了终点，那就说明她在中途超过了某匹更慢的马。

怎么做？

A 一串字母前面的每匹马从自己当前位置 K_i 以最大速度 S_i 跑到终点 D，需要的时间是 (D - K_i) / S_i。

这些马都会按自己的速度走，谁追上别人就降速，但是不用考虑减速的情况，你可以理解为追上前面的马和被追的马是一只马，会同时到达终点，所以只要知道每匹马自己单独跑到终点要多久就够了。设 t_i 为其他马到达终点的时间，那么 A 一串字母的最大合法速度为 D \div \max_{t_i}，能保证她在最长的那个时间内刚好到达终点，不超过任何马。

上代码！

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

#define ll long long
#define ld long double
#define dot(x) fixed<<setprecision(x)
#define foru(a,b,c) for(ll a=b;a<=c;a++)

ll t,n,m,T,d;

int main(){
    cin>>t;
    T=t;
    while(t--){
        cin>>d>>n;
        ld maxx=0;
        foru(i,0,n-1){
            ld k,s;
            cin>>k>>s;
            maxx=max(maxx,(d-k)/s);
        }
        cout<<dot(6)<<"Case #"<<T-t<<": "<<d/maxx<<endl;
    }
    return 0;
}