最近,零崎發現自己的基友們都很閒,於是提議大家來玩一個叫“跑得快”的游戲吧,輸的人就去操場跑三千米。經過一番苦戰,除了跑的最快的jhljx,其他人都要去跑三千米了……
關於長跑,零崎有一個無恥的習慣,那就是緊跟著第一的人跑(如果前面沒人就干脆不跑)。因為學院路這邊的操場上每天都有很多人跑步鍛煉身體,零崎肯定是逃不掉這個三千米的,跑完不過是時間問題。
為了簡化問題,假設這些人跑步都是勻速的,零崎會跟在第一個人後面跑,如果被更快的人超過,零崎會加速跟在那個人後面。那麼零崎到底多久能跑完?
多組輸入數據。
每組輸入數據第一行為一個整數N,為操場上跑步的總人數。
接下來N行每行兩個數Vi,Ti為第i個人的速度(km/h)和出發時間(s)(負數為在零崎之前出發,不考慮超過零崎一圈的情況)
每組輸入數據中至少有一組出發時間非正的數據和一組出發時間非負的數據。
對於每組數據,輸出一行,為零崎跑完三千米的時間,以秒為單位向上取整。
4
20 0
25 -155
27 190
32 200
538
double ceil(double x) 頭文件 math.h / cmath
解題思路:
根據題目要求,不考慮超過一圈的情況,這樣可以把跑道看做一條直線。每個人都是勻速直線地跑步,而你卻是跟著超過你的人跑步。當沒有人在你前面的時候你會覺得沒有動力所以也就站在起點一動不動,直到有人超過你。這時你就跟著這個人一起跑。突然又有一個人超過了你們兩個,所以你決定追上他,跟著新的人跑。按照這個規律下去,直到到達終點。我們現在要做的就是求出到達終點也就是跑3000米需要的時間。
仔細想想,提前出發的人也就是出發時間為負值的人,我們沒有必要把他們考慮進去。第一種情況:如果你能超過他,那麼說明你的速度比他快也就是你能更快的到達終點,不需要跟著他,也就相當於不考慮他了。第二種情況:你沒有追上先出發的那些人,說明你沒有資格跟在他們後面,為什麼沒有資格呢,是因為後出發的人當中沒有人能夠超過他們,也就是你跑完3000米的時間跟他們沒有關系。因此可以將出發時間為負值的那些人當做路人甲,不用管他們。
現在我們需要求出到達終點的時間。因為每次你都能跟著超過你的人,所以直到終點你一直都是最快的,(這裡提示一下,你不是全程都跟著最快的人跑,你這是在路途中不斷地更換最快的人),那麼我們求的時間就是誰最先到達終點,你也就跟著他到達了終點。也就是意味著不用考慮跑步過程中究竟是先跟著誰然後跟著誰,決定你跑步時間的是最先到達終點的(提示一下,這裡最先到達終點的所屬集合是出發時間為非負數,也就是不提前出發的人)。
通過分析很容易得到代碼:
#include <bits/stdc++.h> using namespace std; #define max_size 10000 struct Node{ double v; double t; double time; }; bool cmp(Node a,Node b) { return a.time<b.time; }; Node no[max_size]; int main() { int N;//總人數 while(cin>>N) { for(int i=0;i<N;i++) { cin>>no[i].v>>no[i].t; no[i].v/=3.6; if(no[i].t<0) no[i].v=0.1; no[i].time=no[i].t+(3000.0/(no[i].v)); } sort(no,no+N,cmp); int ans=ceil(no[0].time); cout<<ans<<endl; } }