题解 | #To Fill or Not to Fill#

设置大小为d(总距离)的flag数组，初始值为-1，表示每个地方都不可达 按照价格从低到高的顺序遍历每个加油站，对每个加油站，计算它加满油的情况下能覆盖哪些地方。例如，容量为Cmax，每单位汽油可以跑的距离为Davg，当前遍历到的加油站位置为Di，价格为Pi——则遍历flag数组，把所有flag数组上范围在[Di,Di+Cmax*Davg)内，且值为-1的位置设为Pi/Davg，表示这个位置可达，并且开完这一公里需要花费Pi/Davg。(注意：Pi要设置成double，float的精度不够）

最后从前往后遍历flag数组。如果遇到-1，则无法完成旅行，且第一个-1出现的位置就是能到达的最远距离；如果一直没有出现-1，只要把flag数组每个位置上的值加起来，就是最便宜的总花费了。

这道题而言这个贪心算法应该是最佳。

#include <iostream>
#include <algorithm>

using namespace std;

//习题7.2 To fill or not to fill

struct station{
    double price;
    int station_d;
};
int compare(station x,station y){
    return x.price<y.price;
}

int main(){
    int cmax,d,davg,n;//容量，距离，每单位汽油的距离，加油站数
    int i;
    while(scanf("%d%d%d%d",&cmax,&d,&davg,&n)!=EOF){
        double cost=0;
        double flag[d];
        for(i=0;i<d;i++)
            flag[i]=-1;
        station s[n];
        for(i=0;i<n;i++){
            scanf("%lf%d",&s[i].price,&s[i].station_d);
        }
        sort(s,s+n,compare);
        for(i=0;i<n;i++){//遍历所有加油站
            for(int plot=s[i].station_d;plot<s[i].station_d+cmax*davg && plot<d;plot++)//当前加油站所能覆盖的所有距离
                if (flag[plot]<0)flag[plot]=s[i].price;
        }
        for(i=0;i<d;i++){
            if (flag[i]<0){
                printf("The maximum travel distance = %.2f\n",float(i));
                break;
            }
            cost+=flag[i]/davg;
        }
        if(i==d){
            printf("%.2f\n",cost);
        }
    }
    return 0;
}