指出核心思路

核心思路就是一句话：让最低的油价尽量跑的最远。

先对加油站按油价升序排序，让油价低的排前面。

核心代码如下：

for (int i = 0; i < n; i++) {
	int station_distance = 0; //记录第i个加油站加的油的行驶距离

	int dis = 0;  //从第i个加油站开始最远能跑到哪，要么就是stations[i].di + cmax * davg，要么直接跑到终点
	int max = stations[i].di + cmax * davg;

	if (max < d) dis = max;
	else dis = d;

	for (int j = stations[i].di + 1; j <= dis; j++) { 
		if (ispass[j] == false) { //false说明没走过，那就可以走
			ispass[j] = true;
			//distance++;
			station_distance++;
		}
	}
	cost += (station_distance / davg) * stations[i].pi;
}

我们用一个数组记录每一个单位的距离是否走过，如ispass[j] = false，就代表[ j - 1, j ]这个单位距离没有经过，那我们就可以走，因为我们每次让走的都是当前油价最低的，那么最后总花费就是最低的。

全部的代码如下：

#include <bits/stdc++.h>
using namespace std;

struct station {
	double pi;
	double di;
};

bool cmp(station x, station y) {
	return x.pi < y.pi;
}

int main() {
	double cmax, d, davg;
	int n;
	while (cin >> cmax >> d >> davg >> n) {
		vector<station> stations(n);
		for (int i = 0; i < n; i++) {
			cin >> stations[i].pi >> stations[i].di;
		}

		sort(stations.begin(), stations.end(), cmp); //按照油价升序排序
		vector<bool> ispass(d + 1, false); //判断是否已经走过了[j - 1, j]


		//double distance = 0; //记录总的行驶距离
		

		double cost = 0; //记录总花费

		for (int i = 0; i < n; i++) {
			int station_distance = 0; //记录第i个加油站加的油的行驶距离

			int dis = 0;  //从第i个加油站开始最远能跑到哪，要么就是stations[i].di + cmax * davg，要么直接跑到终点
			int max = stations[i].di + cmax * davg;

			if (max < d) dis = max;
			else dis = d;

			for (int j = stations[i].di + 1; j <= dis; j++) { 
				if (ispass[j] == false) { //false说明没走过，那就可以走
					ispass[j] = true;
					//distance++;
					station_distance++;
				}
			}
			cost += (station_distance / davg) * stations[i].pi;
		}

		bool flag = true; //是否走完的标志位
		double distance = 0;
		for (int i = 1; i <= d; i++) {
			if (ispass[i] == false) {
				flag = false;
				distance = i - 1;
				break;
			}
		}

		if (flag) {
			printf("%.2f\n", cost);
		}
		else {
			printf("The maximum travel distance = %.2f\n", distance);
		}

	}
}