题解 | #To Fill or Not to Fill#

贪心还是要多思考，不然写到后面发现思路是错的

问题分解为每次在加油站加多少油

• ①最大行驶距离内有更便宜的加油站，只需加刚好能到的油
• ②直接能到终点，只需加刚好能到的油
• ③否则将油加满 a、有其他更贵的加油站，寻找相对便宜的加油站 b、输出最大行驶距离

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=510;
struct station{
    double price;
    double dist;
};
bool compare(station x,station y){
	return x.dist<y.dist;
}
station supply[maxn];

int main(){
    int cmax,destination,davg,n;//油箱最大容量、目的地距离、单位油耗可行驶距离、加油站数量
    while(scanf("%d%d%d%d",&cmax,&destination,&davg,&n)!=EOF){
        for(int i=0;i<n;i++){
            scanf("%lf%lf",&supply[i].price,&supply[i].dist);
        }
        sort(supply,supply+n,compare);//按距离升序
       
        double tank=0;//油量 
        double count=0,money=0;//行驶距离、花费 
        double mi=0;
        int j=-1; //所在加油站编号
        if(0==supply[0].dist)j=0;
		else{ //初始位置没有加油站
			printf("The maximum travel distance = 0\n");
			continue;
		}
        
	while(1){
		bool flag=false;
		for(int i=j+1;i<n;i++){//有更便宜的加油站 
			if(supply[i].dist>count+cmax*davg)break;//超出到达距离
			if(supply[i].price<=supply[j].price){
					money+=((supply[i].dist-count)/davg-tank)*supply[j].price;//加油至恰能到达下一个便宜加油站
				   // printf("%.2lf\n",money);//
					tank=0;
				//printf("有更便宜的%d加油站,油价：%lf 空箱达到\n",i+1,supply[i].price); //
				j=i;//更新所在加油站编号
				count=supply[i].dist;//更新行驶距离
				flag=true;
				break; 
			}
		}
		if(!flag){
			if(count+cmax*davg>=destination){//直接到达终点 
				money+=((destination-count)/davg-tank)*supply[j].price;
				printf("%.2lf\n",money);
				break;
			}
			else{//加满油
				money+=(cmax-tank)*supply[j].price;
				//	printf("%.2lf\n",money);//
				tank=cmax;
				int k=-1;//记录相对便宜的加油站编号
				bool flag=false;//记录有无相对便宜的加油站
				for(int i=j+1;i<n;i++){
					if(supply[i].dist<=count+cmax*davg){
						if(flag==false){
							mi=supply[j].price-supply[i].price;
							flag=true;
							k=i;
						}
						else if(supply[j].price-supply[i].price>mi){
							k=i;
							mi=supply[j].price-supply[i].price;
						}
					}
				}
				if(k!=-1){
					tank=cmax-(supply[k].dist-count)/davg;//更新油量
					j=k;
					count=supply[k].dist;//更新行驶距离	
				}
				else{
					printf("The maximum travel distance = %.2lf\n",count+tank*davg);
					break; 
				}
			}
		}
	}
        }
    return 0;
}