题目描述

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

输入输出格式

输入格式：

 

第一行，D1，C，D2，P，N。

接下来有N行。

第i+1行，两个数字，油站i离出发点的距离Di和每升汽油价格Pi。

 

输出格式：

 

所需最小费用，计算结果四舍五入至小数点后两位。如果无法到达目的地，则输出“No Solution”。

 

输入输出样例

输入样例#1：

275.6 11.9 27.4 2.8 2102.0 2.9220.0 2.2

输出样例#1：

26.95 思路

理解：1、如果 当前站点的位置+油箱容量*每升油能行驶的距离
       <下一个站点的位置，那么无法到达目的地2、如果 当前站点油的价格比下一个站点油的价格高，那么先用完油箱里剩余的油，再加油加到恰好可以跑到下一个站点，油箱里不储油3、如果 当前站点油的价格比下一个站点油的价格低，那么就一直跑，跑到碰到一个站点油的价格比它低，或者是跑到能跑到的最远的站。耗油分两种情况： 设到达当前站点时，油箱里有剩余的油，若没有剩余则视为0，不影响 a、邮箱里剩余的油的单价比当前站点的油的单价高，不用剩余的油，用当前站点的油。耗费只加上实际需要的油的价格，同时存储若加满可以省下多少油。 b、油箱里剩余的油的单价比当前站点的油的单价低，先用完剩余的油，再用当前站点的油。耗费加上剩余的油的价格再加上当前站点实际需要的油的价格，同时存储若加可以剩下多少油。几个问题：1、为什么情况2不储存油？因为下一个站点的油的价格更便宜。2、为什么情况2考虑剩余的油的价格直接用？为什么不考虑有无剩余的油？ 假设有3个站点 a，b，c。b为当前站点。 若油价为a>
        b>c，那么在上一个站点不储存油。若油价为a
        c，那么先用剩余的油花费更少。油如果没有，就是0，计算的时候不影响
       

 

 

题解

#include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            using namespace std;//Summary://    在开始前，进行判断，能不能到达最近的加油站，如果不行，No solution//    在当前节点开始往后搜索，如果后面的节点没有比当前结点的单价便宜的，//       就在当前结点加满油，到达能到达的最便宜的节点那//        如果有比当前结点便宜的，那么就在当前结点加有加到刚刚好能到那个油站//            要求到里离当前结点最近的，比当前结点便宜的int main() {    double distance_tmp, capacity, dis_per_liter, price[101];    int n_station;    cin >> distance_tmp >> capacity >> dis_per_liter >> price[0] >> n_station;    double distance[101];    distance[0] = 0;    distance[n_station + 1] = distance_tmp;    for (int i = 1; i <= n_station; i++) {        cin >> distance[i] >> price[i];    }    double usage = 0.0;    //left_oil_capacity放错位置进行初始化了    double left_oil_capacity = 0.0;    for (int current_pos = 0; current_pos <= n_station;) {        //最近的站台都到不了        if (capacity*dis_per_liter < distance[current_pos + 1] - distance[current_pos]) {            cout << "No Solution" << endl;            return 0;        }        double min_price_forward = 0xffff;        int min_price_forward_station = current_pos + 1;        bool found_less_price = false;        for (int next_pos = current_pos + 1; next_pos <= n_station + 1; next_pos++) {            //保证能到下一个节点，否则就跳出            if (capacity*dis_per_liter < distance[next_pos] - distance[current_pos]) {                break;            }            //更新最近更便宜的节点            if (price[next_pos] < min_price_forward) {                min_price_forward = price[next_pos];                min_price_forward_station = next_pos;                //如果有比当前结点便宜的或者相等的                if (price[next_pos] <= price[current_pos]) {                    //加到刚刚好即可                    usage += ((distance[next_pos] - distance[current_pos]) / dis_per_liter - left_oil_capacity)*price[current_pos];                    left_oil_capacity = 0;                    //到更便宜的节点那                    //found_less_price便于判断是否找到了更少油价的节点                    found_less_price = true;                    current_pos = next_pos;                    break;                }            }            if (next_pos == n_station + 1) {                //未来节点没有一个比当前结点便宜的                //并且终点可以直接到达                //那么直接加到刚刚够到达的容量即可                if (min_price_forward > price[current_pos]) {                    //这一部分要用等宽字体来看                    //↓使用费用                 两点距离↓                                       减去还留下的油↓            单价↓                    usage += ((distance[next_pos] - distance[current_pos]) / dis_per_liter - left_oil_capacity)*price[current_pos];                    //到达终点                    cout << setiosflags(ios::fixed) << setprecision(2) << usage << endl;                    //system("pause");                    return 0;                }            }        }        if (found_less_price)continue;        //对于没有的比当前结点便宜的，就加满，到最便宜的下一个节点        usage += (capacity - left_oil_capacity)*price[current_pos];        left_oil_capacity = capacity - (distance[min_price_forward_station] - distance[current_pos]) / dis_per_liter;        current_pos = min_price_forward_station;    }    cout << setiosflags(ios::fixed) << setprecision(2) << usage << endl;    return 0;}
           
          
         
        
       

 

大神代码

#include 
       
        #include 
        
         #include 
         
          using namespace std;double d1,c,d2;int n;double d[100015],p[100015];void DFS(int now,double price,double l_o,double l_o_p){    if(now==n)    {        printf("%.2lf",price);        exit(0);    }        double max_go=c*d2;        if(d[now]+max_go
          
           p[now+1])        DFS(now+1,l_o*l_o_p+((d[now+1]-d[now])/d2-l_o)*p[now],0,0);    else    {        int i,j;        for(i=now+1;i<=n;i++)            if(d[now]+max_go
           
            p[j])    break;        if(j==i+1||j==n+1)    j--;        if(l_o_p>p[now])            DFS(j,price+(d[j]-d[now])/d2*p[now],c-(d[j]-d[now])/d2,p[now]);        else        {            double t_o=(d[j]-d[now])/d2;            t_o-=l_o;            DFS(j,price+t_o*p[now]+l_o*l_o_p,c-t_o-l_o,p[now]);        }    }}int main(){    cin>>d1>>c>>d2>>p[0]>>n;        for(int i=1;i<=n;i++)        cin>>d[i]>>p[i];    d[++n]=d1,p[n]=1000000007;    DFS(0,0,0,0);        return 0;}
           
          
         
        
       

 

本蒟蒻代码