傳送門

?題意

有編號0到n,n+1輛車排隊過紅綠燈，從0到n離交通燈線越來越近

每輛車都有一個最大速度v,車身長度l,和離交通燈線的距離s,

一輛車頭到達線則說明這輛車已到達線

如果一輛車前面沒有緊鄰著一輛車，那么這輛車可以以最大速度行駛

如果前面緊鄰著一輛車，則車頭貼著前一輛車尾行駛，不能超車！

即使過了交通燈線也不能超車！

問第0輛也就是離線最遠的一輛，到達線的最短時間

?思路

既然不能超車，那么最遠的車到線時有兩種可能

①自己到線 $t=\frac{s_{0}}{v_{0}}$

②接在第p輛車后面到線 $\frac{s_{p}+\sum_{1}^{p}l_{i}}{v_{p}}$

解釋一下接在某輛車后面為什么是這樣算

?假設(shè)有兩輛車$a_{1}$速度為$v$,$a_{0}$速度為$2v$

當前面的車到達$p$點時，同時后面的車到達${p}'$ ，兩者所花時間相同

同理可知

當$a_{1}$到達$O$點時，$a_{0}$到達$l_{1}$點，也就是$a_{0}$離終點線的距離是$a_{1}$的車長

②式也就是如果連在了第$p$輛車后面($p$后面的車全都連起來了)

當?shù)?p$輛車到達終點線時，最遠的一輛車離終點線的距離就是$p$后面所有車的車長-最后一輛車自身車長

也就是$sum=\sum_{1}^{p}l_{i}$

所以行駛的時間就是$p$車行駛時間+最遠的車以$v_{p}$行駛$sum$的時間即$\frac{s_{p}}{v_{p}}+\frac{\sum_{1}^{p}l_{i}}{v_{p}}$

由于接在那輛車后面不確定，所以可以算最大的時間，

行駛時間長說明速度慢，后面速度快的肯定會接在他后面

?代碼

1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxn=1e6+6; 4 double l[maxn],s[maxn],v[maxn]; 5 double sum[maxn]; 6 int main() 7 { 8 int n; 9 while(~scanf("%d",&n)) 10 { 11 for(int i=0;i<=n;i++) 12 { 13 scanf("%lf",&l[i]); 14 if(i==0) 15 continue; 16 sum[i]=sum[i-1]+l[i]; 17 } 18 for(int i=0;i<=n;i++) 19 scanf("%lf",&s[i]); 20 for(int i=0;i<=n;i++) 21 scanf("%lf",&v[i]); 22 23 ///單獨過終點 24 double ans=s[0]/v[0]; 25 26 ///排隊過終點 27 for(int i=1;i<=n;i++) 28 ans=max(ans,(s[i]+sum[i])/v[i]); 29 30 printf("%.10f\n",ans); 31 } 32 } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/MMMinoz/p/11599937.html

總結(jié)

以上是生活随笔為你收集整理的hdu 6851 Vacation（思维+贪心）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。