A1033

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 using namespace std;
 5 const int INF=1000000000;
 6 const int maxn=510;
 7 struct station{
 8     double price,dis; //价格、与起点的距离 
 9 }st[maxn];
10 bool cmp(station a,station b){
11     return a.dis<b.dis; //按距离从小到大排序 
12 }
13 int main(){
14     int n;
15     double cmax,d,davg;
16     scanf("%lf%lf%lf%d",&cmax,&d,&davg,&n);
17     for(int i=0;i<n;i++){
18         scanf("%lf%lf",&st[i].price,&st[i].dis);
19     }
20     st[n].price=0; //数组最后放置终点，价格为0
21     st[n].dis=d; //终点距离为d
22     sort(st,st+n,cmp); //所有加油站按距离从小到大排序
23     if(st[0].dis!=0){
24         printf("The maximum travel distance = 0.00n");
25     } else{
26         int now=0; //当前所处的加油站编号
27         //总花费、当前油量、满油行驶最远距离
28         double ans=0,nowTank=0,maxx=cmax*davg; 
29         while(now<n){ //每次循环将选出下一个需要到达的加油站
30         /*选出从当前加油站满油能到达范围内的
31         第一个油价低于当前油价的加油站 */
32         //如果没有低于当前油价的加油站，则选择价格最低的那个 
33             int k=-1;  // 最低油价加油站的编号 
34             double priceMin=INF; // 最低油价
35             for(int i=now+1;
36              i<=n&&st[i].dis-st[now].dis<=maxx;i++){
37                  if(st[i].price<priceMin){
38                      priceMin=st[i].price;//如果油价比当前最低的还低，
39                      //则更新最低油价。 
40                      k=i;
41                      /*如果找到第一个油价低于当前油价的加油站，
42                     直接中断循环*/ 
43                     if(priceMin<st[now].price){
44                         break;
45                     }
46                  }
47              }
48              if(k==-1) break;//满油状态无法找到加油站，退出循环 输出结果
49              /*下面为能找到可到达的加油站k，计算转移花费
50                 need为从now到k所需要的油量*/
51             double need=(st[k].dis-st[now].dis)/davg;
52             if(priceMin<st[now].price){
53                 /*如果加油站k的油价低于当前油价
54                 则只买足够到达加油站k的油*/
55                 if(nowTank<need){
56                     ans+=(need-nowTank)*st[now].price;
57                     nowTank=0;
58                 }else{
59                     nowTank-=need;
60                 }
61             }else{//如果加油站k的油价高于当前油价 
62                  ans+= (cmax-nowTank)*st[now].price;//将油箱加满
63                  nowTank=cmax-need; 
64             }
65             now=k;//到达加油站k，进入下一个循环 
66         }
67         if(now==n){
68             printf("%.2fn",ans);
69         }else{
70             printf("The maximum travel distance = %.2fn",st[now].dis+maxx);
71         }
72     }
73     return 0;
74 }