蓝桥杯 算法训练 ALGO-15 旅行家的预算

算法训练 旅行家的预算  

时间限制：1.0s   内存限制：256.0MB

问题描述

　　一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱是空的）。给定两个城市之间的距离D1、汽车油箱的容量C（以升为单位）、每升汽油能行驶的距离D2、出发点每升汽油价格P和沿途油站数N（N可以为零），油站i离出发点的距离Di、每升汽油价格Pi（i=1，2，……N）。计算结果四舍五入至小数点后两位。如果无法到达目的地，则输出“No Solution”。

输入格式

　　第一行为4个实数D1、C、D2、P与一个非负整数N；
　　接下来N行，每行两个实数Di、Pi。

输出格式

　　如果可以到达目的地，输出一个实数（四舍五入至小数点后两位），表示最小费用；否则输出“No Solution”（不含引号）。

样例输入

275.6 11.9 27.4 2.8 2
102.0 2.9
220.0 2.2

样例输出

26.95

 题目解析：

　　将起点想象成第 0 个加油站，终点想象成 N+1 个加油站
　　　　第 0 个加油站距离起点的距离为 0，第 N+1 加油站距离起点的距离为 D1
　　　　第 0 个加油站的价格为 P，第 N+1 加油站的价格为 0
　　　　根据油箱容量 C 和每升汽油能能行驶的距离 D2 可以计算出油箱加满油可以行驶的最大距离 maxDis

　　无解：（在输入时就判断，尽快找出无解情况）
　　　　如果两个加油站的距离大于加满油可以行驶的最大距离，那么无解

　　有解：
　　　　从当前位置的下一个加油站寻找距离最近且便宜的加油站：
　　　　　　1. 如果能找到了
　　　　　　　　（1）如果能一次加油到达，那么加到刚好能到达便宜的加油站即可
　　　　　　　　（2）如果一次不能到达，那么先将油箱加满，到达行驶最大距离之前的那个加油站，再加到刚好行驶到的便宜那个加油站
　　　　　　2. 如果没找到，则加满油，行驶到最大距离之前的那个加油站，继续寻找
　　　　注意：终点的加油站价格为 0，所以最后一次加油加到刚好到达终点即可

示例代码：

 #include<iostream>
 #include<cstdio>
 using namespace std;

 #define MAX_NUM  1001

 int main()
 {
     int N;
     double D1, C, D2, P;
     scanf("%lf%lf%lf%lf%d", &D1, &C, &D2, &P, &N);

 //    double * distance = new double[N+5];    //加油站i到起点的距离
 //    double * price = new double[N+5];          //油的价格
     double  distance[MAX_NUM];
     double  price[MAX_NUM];

     distance[] = ;            //记录第i个点离出发点的距离
     price[] = P;                //起点的油价
     distance[N+] = D1;            //终点为最后一个加油站
     price[N+] = ;                //终点价格 

     double total = ;            //费用
     double surplus=;            //到第i个加油站的时候的剩余油量
     double maxDis = C * D2;        //加满油行使的最大距离
     bool flag = true;            //是否有解，默认有解 

     for (int i = ;i <= N; i++)
     {
         scanf("%lf%lf", &distance[i], &price[i]);
         if (distance[i] - distance[i-] > maxDis)    //如果两个加油站的距离大于加满油可以行使的距离 ，则无解
         {
             flag = false;    //无解
         }
     }

     if(!flag)    //无解
     {
         printf("No Solution\n");
         return ;
     }

     /*
         i:当前加油站的编号
         j：下一个比自己便宜的加油站的编号
     */
     for (int i = , j; i <= N; i = j)    //到达j之后，将j赋值给i，重新循环，知道到达终点
     {
         for (j = i + ; j <= N + ; j++)    //从i的下一个开始找比它便宜的加油站
         {
             if (distance[j] - distance[i] > maxDis)    //如果不能行使到比它便宜的加油站
             {
                 j--;                        //则先行驶到便加满油后能驶得最大距离之前的加油站
                 break;
             }
             if (price[j] <= price[i])        //找比现在所在的加油站便宜的加油站
             {
                 break;
             }
         }

         /*
             从当前位置的下一个加油站寻找距离最近且便宜的加油站：
             1 如果能找到了
                 （1）如果能一次加油到达，那么加到刚好能到达便宜的加油站即可
                  （2）如果一次不能到达，那么先将油箱加满，到达行驶最大距离之前的那个加油站，再加到刚好行驶到的便宜那个加油站
             2 如果没找到，则加满油，行驶到最大距离之前的那个加油站，继续寻找
         */

         if (price[j] <= price[i])    //属于（1）
         {
             total += ((distance[j] - distance[i]) / D2 - surplus) * price[i];    //加到可以刚好行使到 j 点
             surplus = ;                                    //剩余油量
         }
         else    //属于（2）或 2
         {
             total += (C - surplus) * price[i];                //油箱加满
             surplus = C - (distance[j] - distance[i]) / D2;    //到j点时剩余油量
         }
     }

     printf("%.2lf\n", total);

     return ;
 }