【題目鏈接】

ybt 1227：Ride to Office
OpenJudge NOI 4.6 2404:Ride to Office
原題是英文題，雖說兩題題意相同，但一本通網站沒有對該問題進行直譯，名字都不一樣。而且描述不夠完整。我在這里再翻譯一下。

【題目翻譯】

騎車上班

描述

許多員工住在一個叫做M小區的地方，距離他們的單位很遠（4.5公里）。由于交通堵塞，許多員工選擇騎車。
我們可以假設除了魏威以外所有員工都以恒定的速度從家騎到單位。魏威這個人有不同的騎車習慣——他總是試圖跟著其他騎車的人而不是自己單獨騎車。當魏威到達M小區的大門時，他會尋找其它正要出發去單位的人。如果他找到了，他會騎車跟著那個人，否則，他會等待可以跟隨的人。在從家到單位的路上，任何時刻只要有一個騎得更快的人超過了魏威，那么他會離開他正在跟隨的騎行者，并加速去追那個騎得更快的人。
我們假設魏威到達M小區大門的時間是0。給定其它人的出發時刻和速度，你的任務是給出魏威到達單位的時間。

輸入

有多組測試樣例。每個測試樣例的第一行是$N(1\le N\le 10000)$，代表騎行者的數量（除了魏威）。
當$N=0$時結束輸入。接下來的N行是N個不同騎行者的信息，形式如下：
Vi [TAB] Ti
Vi 是一個小于等于40的正整數，表示第i個騎行者的速度（kph，公里/小時）。Ti是第i個騎行者的觸發時間，是一個整數，單位是秒。任何樣例都可以保證總是有一個非負的Ti。

輸出

對每個樣例輸出一行：魏威的到達時間。當遇到分數時，向上取整。

【題目考點】

1. 貪心

【解題思路】

記$t_0$為魏威的出發時間，他的出發時間為大于等于0的騎行者出發時間中的最小值。

出發時間$t_x$早于魏威出發時間$t_0$的人$x$（即$t_x<t_0$），一定不會被魏威跟隨同時到達終點。
有兩種情況：
(1)如果魏威的速度小于或等于$x$的速度，那么魏威一定追不上$x$，不會與他同時到達終點。
(2)如果魏威的速度大于騎行者x的速度，他仍然可能追不上$x$。如果在騎行過程中追上了$x$，他就會超過$x$。由于魏威只會跟隨速度大于等于他的騎行者，所以他不會跟隨$x$。

在出發時間等于或晚于魏威出發時間的騎行者中，只要有超過魏威的騎行者，魏威就會跟上那個人。如果把這個過程看做自行車比賽，魏威就會一直跟著比賽過程中排在第一名的騎行者，因而魏威也一定會跟著第一個沖到終點的騎行者。
所以魏威從出發到到達單位的總時間，就是出發時間等于或晚于魏威出發時間($t_x\ge 0$)的騎行者中，第一個到達終點4500m位置的騎行者的騎行時間。
根據：速度*時間=路程，如果$v_x$為某騎行者的速度，$t_x$為該騎行者的出發時刻，$t_{arr}$為到達終點的時刻，$s$為路程，那么有
$s=v_x?(t_{arr}?t_x)$
求$t$，有$t_{arr}=\frac{s+v_x?t_x}{v_x}$
已知s為4500，求滿足$t_x\ge 0$的$x$中，求出的$t_{arr}$的最小值。

【題解代碼】

解法1：求滿足$t_x\ge 0$的$x$中，$\frac{s+v_x?t_x}{v_x}$的最小值。

#include<bits/stdc++.h> using namespace std; #define N 10005 #define INF 1e9 int main() {int n;double v[N], t[N];//v:速度，單位m/s while(cin >> n && n != 0){ double tmin = INF, time;for(int i = 1; i <= n; ++i){cin >> v[i] >> t[i];v[i] *= 5.0/18;//單位從km/h變為m/s if(t[i] >= 0)//找出發時間等于或晚于st_i的騎手中tmin = min(tmin, 4500/v[i]+t[i]);//求出i到達終點的時刻中的最小值 }cout << ceil(tmin) << endl;}return 0; } 新人創作打卡挑戰賽發博客就能抽獎！定制產品紅包拿不停！

總結

以上是生活随笔為你收集整理的信息学奥赛一本通 1227：Ride to Office | OpenJudge NOI 4.6 2404:Ride to Office的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。