题解 | #To Fill or Not to Fill#(c++)

要点：多用便宜油，贵的油能少用就少用

先将站点按离杭州（起点）的距离排序（距离相同时价格低的优先） 从第一个站点开始，若第一个站点距离不为0，说明起点没有加油站，跑不动，返回能跑的最远距离0

否则进行循环，循环结束的条件：1.当前位置是最后一个站点 2.无法到达下一站点 3.当前站点加满油可达终点且之后再无比当前站点更便宜的站点

一次循环：从当前站点开始向后遍历，在加满油可达的距离内, 1.若出现比当前站点更便宜的站点minIdx，结束遍历并只加油到可以到达minIdx即可（尽量少消耗贵油），将当前站点更新为minIdx，继续循环直到出现结束的条件。2.若在可达距离内所有站点价格都比当前站点贵，则在当前站点加满油（尽量多用便宜油），前往可达距离内价格最低的下一站点（剩下的油量是满油减去消耗掉的油），将此结点更新为当前站点，继续循环直到出现结束的条件。3.当下一站点超出了从当前站点加满油可达的范围时，结束此次遍历

#include<iostream>
#include<algorithm>

#define MAX 500

using namespace std;

struct station{
	double price;
	double dis;
};

bool Compare(station s1, station s2){
	if(s1.dis==s2.dis)
		return s1.price<s2.price;
	else
		return s1.dis<s2.dis;
}

// 确保每段路都是最便宜的
int main(){
	// cmax油箱的最大容量  d杭州到目的地城市的距离
	int cmax, d, davg, n;   // davg汽车每单位油量能跑的平均距离  n加油站总数
	station stats[MAX];
	while(cin>>cmax>>d>>davg>>n){
		// pi，单价，di (<=D)，本站到杭州（起点）的距离
		for(int i=0; i<n; i++)
			cin >> stats[i].price >> stats[i].dis;
		sort(stats, stats+n, Compare);
        if(stats[0].dis!=0){
        	printf("The maximum travel distance = 0\n";
            continue;
        }
		int dmax = cmax*davg;  // 能跑的最大距离
		int idx_now = 0;  // 当前所处站点
		double totalprice = 0;  // 所花费钱数
		double remain_oid = 0;  // 剩余油量
		int minidx;
		while(1){  // 最后一站或下一站不可达或可达终点且从当前站点出发不再有比它便宜的站点
			if(idx_now+1==n)
				break;  // 最后一个站点
			minidx = idx_now+1;   // 当前可达距离内的最便宜的站点下标
			int i, flag=0;
			// 选站点
			for(i=idx_now+1; i<n; i++){
				// 下一站点与当前站点间距离,大于则不可达
				if(stats[i].dis-stats[idx_now].dis>dmax){
					break;
				}
				if(stats[i].price<stats[idx_now].price){ // 有价格更低的站点则换那个
					minidx = i;
					flag = 1; // 算i
					break;
				}
				if(stats[i].price<stats[minidx].price)
					minidx = i;  // 没出现价格更低的站点则算minidx
			}
			// 更新
			if(flag){   // 有价格更低的站点，则只加去这个站点的油
				double require_oid = (stats[minidx].dis-stats[idx_now].dis)/davg;
				if(require_oid > remain_oid){  // 所需油量>剩余油量
					totalprice += (require_oid-remain_oid)*stats[idx_now].price;
					remain_oid = require_oid;
				}
				remain_oid -= require_oid;
				idx_now = minidx;
			}else{  // 没有价格更低的站点
				if(i==idx_now+1)  // 下一个站点不可达
					break;
				else if(d-stats[idx_now].dis<dmax)  // 当前站点可达终点且没有更便宜的站点
					break;
				// 在当前站点把油加满，去最便宜的那个站点,即下标为minidx的
				totalprice += (cmax-remain_oid)*stats[idx_now].price;
				remain_oid = cmax-(stats[minidx].dis-stats[idx_now].dis)/davg;
				idx_now = minidx;
			}
		}

		// 输出结果   是最后一个站点或当前站点可达终点且最便宜/不可达下一站点
		if(d-stats[idx_now].dis>dmax)
			printf("The maximum travel distance = %.2f\n", stats[idx_now].dis+dmax);
		else{
			double require_oid = (d-stats[idx_now].dis)/davg;
			if(require_oid > remain_oid)
				totalprice += (require_oid-remain_oid)*stats[idx_now].price;
			printf("%.2f\n", totalprice);
		}
	}

	return 0;
}