codeup4.4贪心——to fill or not to fill

With highways available, driving a car from Hangzhou to any other city is easy. But since the tank capacity of a car is limited, we have to find gas stations on the way from time to time. Different gas station may give different price. You are asked to carefully design the cheapest route to go.

Input Specification:

Each input file contains one test case. For each case, the first line contains 4 positive numbers: Cmax(≤ 100), the maximum capacity of the tank; D (≤30000), the distance between Hangzhou and the destination city; D​avg​​(≤20), the average distance per unit gas that the car can run; and N (≤ 500), the total number of gas stations. Then N lines follow, each contains a pair of non-negative numbers: P​i
​​, the unit gas price, and D​i​​(≤D), the distance between this station and Hangzhou, for i=1,⋯,N. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print the cheapest price in a line, accurate up to 2 decimal places. It is assumed that the tank is empty at the beginning. If it is impossible to reach the destination, print The maximum travel distance = X where X is the maximum possible distance the car can run, accurate up to 2 decimal places.

注意点：

1. 引入剩余油量的概念。这样当车行驶到某个加油站时如果还剩油，就无需加最大容量的汽油量，只需加到与最大容量的差即可。
2. 该题的难点是怎么寻找“贪心策略”。（算法笔记上有详细说明）

2.1 为什么会想到贪心：我们把加油站的结构体数组按距离排序后发现它与区间问题类似，每个加油站都有一个“作用范围”，（作用范围指从当前站cur出发，加满油以后能行驶的最大距离touch,作用范围为[cur,cur+touch],可以看到等价于区间问题：在每个子问题（区间）里选择最佳的结果（最小油价），进而得到总问题的最佳结果，这正是贪心的思想。
2.2 什么情况下不能到达目的地？两种情形：1. 没有距离为0的加油站，这时候汽车根本启动不了；2.在加油站按照距离排序后，某个加油站的“作用范围”内没有任何加油站，汽车在高速公路上没油。
2.3 为了让汽车最后必然以目的地为终点，因此可以把目的地看作一个虚拟的加油站，其距离等于总距离，其油价为0，这样，目的地的油价肯定是最便宜的。
2.4 贪心策略：从头（第一个）遍历加油站，如果：
（1）在该加油站作用范围内找到油价比当前低的站点，则设置一个布尔变量change,置为真，然后更替最小价格加油站的下标和最小价格。然后退出循环（为啥要退出循环：假设当前加油站是a，加油站距离按a<b<c排序。经过遍历后发现油价大小是c<b<a，虽然c的价格是最小的，但它距离当前加油站a最远，需要加a站的油也更多（油价最高）。还不如先抵达b,再抵达c)。到达油价比当前低的下一个站点后，剩余油量肯定是0
(2) 如果找不到，则change=false，然后从当前站点之后的下一个站点开始找，在满足当前站点的作用范围内，寻找在这其中的所有加油站中油价最低的那个（但肯定比油价高），然后加满油（因为当前油价在作用范围内是最低的），到达该加油站。这个时候，肯定会剩油，或刚好不剩，计算剩油量。
（3）最后更新touch，代表下一加油站的作用范围。

3. 细节问题
   （1）在每次加油时，都应当判断是否余油。因此代表油量的变量应该和总花费一样，设在main函数里或是在全局中。如果不判断是否剩油，很可能会多算总花费。
   （2）同理，因为最后要根据一些布尔变量来决定输出结果，因此这些布尔变量同样应该设置在main函数里，或在全局中。
   （3）最后需要对是否存在距离为0的加油站来进行特判。如果没有距离为0的加油站，则输出0；

代码如下：

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

struct Node{
    double price;
    double dis;
}station[510];

bool cmp(Node a,Node b)
{
    return a.dis<b.dis;
}

bool hasZero=false; //是否存在距离为0的加油站
bool status;    //判断是否有加油站在作用范围内 

int main(void)
{
    double cmax,allDis,per;
    int n;
    cin>>cmax>>allDis>>per>>n;
    for(int i=0;i<n;i++)
    {
        scanf("%lf%lf",&station[i].price,&station[i].dis);
        if(station[i].dis==0) hasZero=true; 
    }
    //增设虚拟的终点加油站
    station[n].price=0;
    station[n].dis= allDis;
    //根据距离排序
    sort(station,station+n+1,cmp); 
    //初始化
    double min_price=station[0].price;
    int min_index=0;
    const double dmax=cmax*per;
    double touch=station[0].dis+dmax;   //在某个加油站加满油后能行驶的最大距离 
    double totalCost=0; //总花费 
    double leave=0;     //剩余油量 
    while(min_index<n)
    {
        status=false;   //默认为在作用范围外 
        bool change=false;  //判断在作用范围内是否有比当前加油站油价更低的站点 
        int end_index;  //记录如果找不到比当前低价的油站时，遍历的最后下标 
        //记录当前加油站的下标和价格 
        double cur_price=station[min_index].price;
        int cur_index=min_index;
        for(int j=min_index+1;j<=n&&station[j].dis<=touch;j++)
        {
            status=true;    //只要进入循环，status就为真
            if(station[j].price<min_price)
            {
                change=true;    //在作用范围内找到了离当前加油站更为便宜的
                min_index=j;
                min_price=station[j].price;
                break;  //退出循环 
            } 
        }
        if(status==false) break;//在加满油后找不到下一个加油站，则退出循环 
        if(change==true)
        {
            double need=(station[min_index].dis-station[cur_index].dis)/per;    //需要恰好能行驶到下一加油站的油量
            if(!leave)  //如果油没有剩余 
            {
                totalCost+=cur_price*need;  //所需油费 
            } else{
                totalCost+=cur_price*(need-leave);
            }  
            leave=0;    //油不会有空余 
        }
        else{
            min_index++;    //前进一位 
            min_price=station[min_index].price;
            for(int k=min_index;k<=n&&station[k].dis<=touch;k++)    //在当前加油站作用范围内寻找油价次低的加油站 
            {
                if(station[k].price<min_price) 
                {
                    min_index=k;
                    min_price=station[k].price;
                }
            }
            if(!leave) totalCost+=cur_price*cmax;       //肯定要加满油，因为在作用范围内找不到油价更低的，不如在当前加油站就把油加满
            else totalCost+=cur_price*(cmax-leave);     //如果之前剩油，那就加到cmax，计算该部分油量 
            leave=cmax-((station[min_index].dis-station[cur_index].dis)/per);       //肯定会剩油 
        }
        touch=station[min_index].dis+dmax;  //作用范围更改
    }
    //输出结果 
    if(hasZero==false||status==false) {
        //注意需要对是否有距离杭州为0的加油站的特判，该情况下无法加油启动，没有行驶距离 
        if(hasZero==false) printf("The maximum travel distance = %.2f\n",0.00);
        else printf("The maximum travel distance = %.2f\n",touch);
    }else{
        printf("%.2f\n",totalCost);
    }
}