算法实验题 4.2 骑行问题
★问题描述：
小马哥是一名骑行爱好者。他准备骑行 4.5km，从 A 地出发前往 B 地。
从 A 地前往 B 地的路上还有很多的单车一族，假设除小马哥外，其他人的速度总是固定
的。小马哥现在在 A 地，他会在那等待一个也是到 B 地骑行的人，然后跟上他。并且和他同
样的速度前往 B 地。在此期间，如果没有人超过小马哥速度，则小马哥保持速度直到到达目
的地。如果有人骑行速度超过小马哥并且从小马哥身边超过，则小马哥会立即加速跟上速度
更快的人，和他一起骑行。
★实验任务：
假设小马哥到达 A 地时的时刻是 0 秒，给你其它骑行者从 A 点出发时的速度和时刻，请
你计算小马哥到达 B 地时的时刻。
★数据输入：
每组测试数据第一行包含一个整数 N(1 <= N <= 10000)，表示从 A 地到 B 地骑行的人
有 N 个。接下来 N 行，每行两个整数 V（0<V<=40）和 T，表示某个骑行者的速度（km/h）以
及该骑行者从 A 点出发时的时刻（秒）。每组测试数据中保证至少包含一个骑行者的 T>=0。
★结果输出：
输出小马哥到达 B 地时的时刻（秒），向上取整。
输入示例 输出示例
4 780
20 0
25 -155
27 190
30 240

 1 #include<stdio.h>
 2 #include<math.h>
 3 #define eps 1e-10
 4 int main()
 5 {
 6     int n,i,j;
 7     double s[10010],t[10010],v[10010][2],len=4500,vm=0,kmh=5.0/18.0;
 8     double si,ti,vmr,sir,tir;
 9     scanf("%d",&n);
10     t[0]=999999999.0;
11     vm=0.0;
12 
13     for(i=1;i<=n;i++){
14         scanf("%lf %lf",&v[i][0],&v[i][1]);
15         v[i][0]*=kmh;//转化为m/s
16         if(v[i][1]<=t[0]&&v[i][1]>=0&&v[i][0]-vm>eps){
17             t[0]=v[i][1];//马哥起步时间
18             vm=v[i][0];//马哥起步速度        
19         }
20     }
21 
22     s[0]=0;//最开始的位置
23     i=0;
24     //printf("起步速度vm=%.2lf t=%.2lf s=%.2lf\n\n",vm,t[0],s[0]);
25     while(s[i]<=4500){
26         i++;
27         sir=45000;
28         tir=999999;
29         vmr=vm;
30         for(j=1;j<=n;j++){
31             if(v[j][0]==vm){
32             //    printf("当前速度是第%d人\n",j);
33                 continue;
34             }
35             si=(v[j][1]-t[i-1]+(s[i-1]/vm))*(vm*v[j][0]/(v[j][0]-vm));
36             ti=(si/v[j][0])+v[j][1];
37             if(si<sir&&si<=4500&&si>s[i-1]&&ti>0&&ti-t[i-1]>eps&&v[j][0]-vm>eps)
38             {
39                 sir=si;
40                 tir=ti;
41                 vmr=v[j][0];
42                 //printf("ti=%.2lf t[i-1]=%.2lf\n",ti,t[i-1]);
43             }
44         //    printf("j=%d s=%.2lf t=%.2lf vmr=%.2lf\n",j,si,ti,vmr);
45         }
46         vm=vmr;
47         s[i]=sir;
48         t[i]=tir;
49         //printf("minlen=%.2lf mintime=%.2lf vm=%.2lf\n\n",s[i],t[i],vm);
50     }
51     double ans=(4500-s[i-1])/vm+t[i-1];
52     printf("%.0lf\n",ceil(ans));
53     return 0;
54 }