1033. To Fill or Not to Fill (25)

题目连接：https://www.patest.cn/contests/pat-a-practise/1033

这道题对我来说够难了，一开始觉得是最短路径，后来发现不对劲，看了其他人的解法才知道是贪心，其逻辑关系得理清：

1、找到当前站点的所有可以到达的点

2、如果有可以到达的站点

2-1找离得近的比当前站点便宜的站点，把油加到该站点即可（前提是终点大于该站点）；

2-2如果没有比当前站点便宜的点：

2-2-1如果当前站点可以到达终点，则油加到此量即可；

2-2-2如果当前站点无法到达终点，油加满；

3、如果没有可以到达的站点

3-1如果可以到达终点，将油加到此量即可；

3-2如果不能到达终点，求最大距离。

  1 #include<stdio.h>
  2 #include<stdlib.h>
  3 #define MAXN 505
  4 #define INFINITY 400005
  5 
  6 typedef struct SNode{
  7     float price;
  8     int distance;
  9 }st;
 10 st station[MAXN];
 11 
 12 int Cmax,D,Davg,N;
 13 int maxgans,remaingas=0;
 14 
 15 int cmp(const void *a,const void *b)
 16 {
 17     return ((*(st*)a).distance-(*(st*)b).distance);
 18 }
 19 
 20 int Isreach(int index,int dst)
 21 {
 22     if (maxgans>=(station[dst].distance-station[index].distance))return 1;
 23     else return 0;
 24 }
 25 
 26 int main()
 27 {
 28     scanf("%d %d %d %d",&Cmax,&D,&Davg,&N);
 29     int i;
 30     maxgans=Cmax*Davg;
 31     if (D==0){printf("0.00");return 0;}
 32     if (N==0){printf("The maximum travel distance = 0.00");return 0;}
 33     for (i=0;i<N;i++)
 34     {
 35         scanf("%f %d",&station[i].price,&station[i].distance);
 36     }
 37 
 38     qsort(station,N,sizeof(station[0]),cmp);
 39     station[N].distance=INFINITY;station[N].price=INFINITY;
 40 
 41     if (station[0].distance!=0){printf("The maximum travel distance = 0.00");return 0;}
 42 
 43     int index=0,j,flag=0;
 44     float money=0,length=0;
 45     while (1)
 46     {
 47         flag=0;
 48         for (j=index+1;j<=N;j++)
 49         {
 50             if (Isreach(index,j)&&station[j].distance<=D)
 51             {
 52                 flag=1;
 53               //  printf("%d ",index);
 54                 if (station[j].price<station[index].price)  //价格比当前少
 55                 {
 56                     money+=(station[index].price*(station[j].distance-station[index].distance-remaingas)/Davg); //printf("%.2f ",money);
 57                     remaingas+=(station[j].distance-station[index].distance-remaingas);
 58                     break;
 59                 }
 60                 else  //价格比当前贵
 61                 {
 62                     if (!Isreach(index,j+1))   //价格比当前贵的最后一个站点（说明当前站点所到达的范围内没有比当前站点便宜的）
 63                     {
 64                         if (maxgans+station[index].distance>=D)  //如果从当前站点可以到达终点
 65                         {
 66                             money+=(station[index].price*(D-remaingas-station[index].distance)/Davg);
 67                             flag=0;
 68                             break;
 69                         }
 70                         money+=((station[index].price*(maxgans-remaingas)/Davg));//当前站点不能到达终点， 加满;
 71                         remaingas=maxgans;
 72                         break;
 73                     }
 74                 }
 75             }
 76             else  //当前站是最后一站或者当前战到达不了下一站或者目标低点小于下一站
 77             {
 78                 if (station[index].distance+maxgans>=D)  //可以到达
 79                 {
 80                     flag=0;
 81                    // printf("zuihou :%.2f %.2f",money,(station[index].price*(D-station[index].distance-remaingas)/Davg));
 82                     money+=((station[index].price*(D-station[index].distance-remaingas)/Davg));
 83                     break;
 84                 }
 85                 else  //无法到达
 86                 {length=station[index].distance+maxgans;flag=0;
 87                 break;
 88                 }
 89             }
 90         }
 91         //printf("
");
 92         if (flag)
 93         {remaingas-=(station[j].distance-station[index].distance);//printf(" %d 
",remaingas);
 94         index=j;}
 95         else if (flag==0)break;
 96     }
 97 
 98     if (length==0)printf("%.2f",money);
 99     else if (length!=0)printf("The maximum travel distance = %.2f",length);
100     return 0;
101 }