PAT A1033 To Fill or Not to Fill

解题思路

说实话，这道题目是一道小学数学题，理解较为容易，但是用代码实现有点难。首先将数据保存到一个数组中，然后判断第一个距离是不是为0，如果不为0，直接输出一句话“The maximum travel distance = 0.00”，并结束程序。

然后主要利用两个位置，一个now表示前一个位置，另一个ind表示下一步要走的位置。每次都从now往后遍历，记录价格最小的位置，遍历要加一个条件，就是下一个位置的距离要小于前一个位置now加满油状态下能走的最远距离。找出价格最小的位置ind，如果价格小于now的价格直接退出for循环。如果满油状态下找不到加油站，就退出while循环，打印最远距离。

找出了下一步要到的加油站，接下来就是计算花费。首先算出根据到下一站的距离，计算出需要多少油量need，然后用一个nowTank变量保存当前油箱的油量，然后分两种情况，一个是下一站油费小于当前油费时，就只需要加油到下一站即可，然后到下一站再加，这样更便宜，需要进一步判断油箱里的油是不是大于need，如果是就不需要计费，nowTank直接减去need，如果不是，就需要加油计费。然后如果大于下一站油费时，就加满油箱，然后减去need需要的即可。

代码

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=510;
const int INF=1e9;
struct Station{
    double price,d;
}stas[maxn];
double Cmax,dest,aved;
int n;

bool cmp(const Station& a,const Station& b){
    return a.d<b.d;
}
int main(){
    scanf("%lf%lf%lf%d",&Cmax,&dest,&aved,&n);
    for(int i=0;i<n;i++){
        scanf("%lf%lf",&stas[i].price,&stas[i].d);
    }
    sort(stas,stas+n,cmp);
    stas[n++].d=dest;stas[n].price=0.0;
    int now=0;
    double total_d=Cmax*aved;
    if (stas[0].d!=0.0){
        printf("The maximum travel distance = 0.00");
        return 0;
    }
    double total_price=0.0,nowTank=0.0,MAX=Cmax*aved;
    while(now<n-1){
        double min_price=INF;
        int ind=-1;
        for(int i=now+1;i<n;i++){
            if(stas[now].d+total_d>=stas[i].d){//当前距离+每次加满能到的距离
				if (stas[i].price<min_price){
				    min_price=stas[i].price;
				    ind=i;
				    if(min_price<stas[now].price){
                        break;
				    }
				}
            }
        }
        if (ind==-1) break;
        double need=(stas[ind].d-stas[now].d)/aved;//计算从now到ind需要的油量
        if (min_price<stas[now].price){//如果油价小于now的油价，只需加油到下一站
            if (nowTank<need){//如果油箱中的油量小于需求量
                total_price+=(need-nowTank)*stas[now].price;
                nowTank=0;//加油使刚好到下一站
            }else{//油箱中剩余油量足够到下一站，不需要加油
                nowTank-=need;
            }
        }else{//如果油价大于now，需要加满油
            total_price+=(Cmax-nowTank)*stas[now].price;
            nowTank=Cmax-need;
        }
        now=ind;
    }

    if (now==n-1){
        printf("%.2f",total_price);
    }else{
        printf("The maximum travel distance = %.2f",stas[now].d+MAX);
    }
    return 0;
}