1033 To Fill or Not to Fill

With highways available, driving a car from Hangzhou to any other city is easy. But since the tank capacity of a car is limited, we have to find gas stations on the way from time to time. Different gas station may give different price. You are asked to carefully design the cheapest route to go.

Input Specification:

Each input file contains one test case. For each case, the first line contains 4 positive numbers: Cmax​ (≤ 100), the maximum capacity of the tank; D (≤30000), the distance between Hangzhou and the destination city; Davg​ (≤20), the average distance per unit gas that the car can run; and N (≤ 500), the total number of gas stations. Then N lines follow, each contains a pair of non-negative numbers: Pi​, the unit gas price, and Di​ (≤D), the distance between this station and Hangzhou, for i=1,⋯,N. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print the cheapest price in a line, accurate up to 2 decimal places. It is assumed that the tank is empty at the beginning. If it is impossible to reach the destination, print The maximum travel distance = X where X is the maximum possible distance the car can run, accurate up to 2 decimal places.

Sample Input 1:

50 1300 12 8
6.00 1250
7.00 600
7.00 150
7.10 0
7.20 200
7.50 400
7.30 1000
6.85 300

Sample Output 1:

749.17

Sample Input 2:

50 1300 12 2
7.10 0
7.00 600

Sample Output 2:

The maximum travel distance = 1200.00

 贪心：

将目的地当作第n个站点，价格为0；

将所有站点按距离排序；

在当前站点的最大里程范围里搜寻价格最低站点：1）如果遇到比当前站点价格低的站点立即前往（也许它不是在里程范围里最低的，但是这样做比找到里程范围里最低的然后前往花钱要少，因为站点是按照距离排序的，按照贪心算法，只考虑当前的小范围，保证每一步的花费是最小的，也就是说能省一步是一步）；2）如果都比当前站点价格高那就是找到最小的；

如果k==-1说明当前里程范围无法到达任何一个站点，直接退出while循环，输出当前站点距离+最大里程；

下一步计算当前到下一个站点要加多少油：1）如果下一个站点比当前站点更便宜，那就加刚好可以到达下一站点的油；2）如果不是，那就在当前站点加满，这样能保证至少到达下一站点前用的油是最便宜的（贪心，只考虑当前小范围）；

注意更新当前油量和花费。

#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std;
int n;
double cost, c, x, d, da;

int now;//当前站点
double limit;//续航最大里程
double nowc;//当前油量
struct Station {
	double p;//单位价格
	double dis;//距离
} a[1000];

bool cmp(Station s1, Station s2) {
	return s1.dis < s2.dis;
}

int main() {
	cin >> c >> d >> da >> n;
	limit = c * da;
	for (int i = 0; i < n; i++) {
		cin >> a[i].p >> a[i].dis;
	}
	a[n].p = 0;
	a[n].dis = d;
	sort(a, a + n, cmp);
	if (a[0].dis > 0.0) {
		cout << "The maximum travel distance = 0.00";
		return 0;
	}
	while (now < n) {
		double minn = 1.0e10; //最低价格
		int j = -1; //最低价格对应站点
		for (int i = now + 1; i <= n && a[i].dis - a[now].dis <= limit; i++) {
			if (a[i].p < minn) {
				minn = a[i].p;
				j = i;
				if (minn < a[now].p) {
					break;//找到比当前价格更低加油站，立即前往
				}
			}
		}
		if (j == -1) {
			break;//无法到达
		}
		double need = (a[j].dis - a[now].dis) / da;
		if (minn < a[now].p) {
			if (nowc < need) {
				cost += (need - nowc) * a[now].p;
				nowc = 0;
			} else {
				nowc -= need;
			}
		} else {
			cost += (c - nowc) * a[now].p;
			nowc = c - need;
		}
		now = j;
	}
	if (now == n) {
		cout << setprecision(2) << fixed << cost;
	} else {
		cout << "The maximum travel distance = " << setprecision(2) << fixed << a[now].dis + limit;
	}
	return 0;
}