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.

输入描述:

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.

输出描述:

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.
示例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
50 1300 12 2
7.10 0
7.00 600
输出

749.17
The maximum travel distance = 1200.00

分析：这题基本思路采用贪心策略，但是注意点很多

思路：
1.按照距离远近，由远到近进行排序
2.在贪心过程中主要考虑一下2种情况：
1.没有在能跑的最大距离中找到比当前更便宜的加油站，就直接加满，然后跑到较便宜的加油站。（因为当前的油最便宜）
2.如果在能跑的最大距离中有比当前更便宜的加油站：如果剩余油量支持跑到更便宜的站，当前就不加油；如果不支持，就加油到刚好跑到下一站再加。

注意点：

1. 在做这道题时，最容易忽略的就是要记录当前剩余油量。油量充足，中间可以不加油，不是每到一个站都必须加油。造成我走了很多弯路
2. 采用double。用float精度不够，在某一些数据数据较大的例子中无法通过。
3. 找cheapest（情况1下，在一个阶段中较便宜的加油站）,nearest（情况2下，最近较便宜的加油站）时，用<=，因为要尽量跑的更远。（具体见代码解释）

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<queue>
#include<stack>
#include<cctype>
#include <unordered_map>
using namespace std;
struct gas
{
	double price;
	double dis;
};
bool comp(gas a, gas b){
	if(a.dis == b.dis){
		return a.price < b.price;
	}
	return a.dis < b.dis;
}
int main(int argc, char const *argv[])
{
	double cmax,d,davg,n;
	while(cin>>cmax>>d>>davg>>n){
		vector<gas> station(n+1);
		for (int i = 0; i < n; ++i)
		{
			cin>>station[i].price>>station[i].dis;
		}
		station[n].price = 0;			//将终点站也看成加油站
		station[n].dis = d;
		sort(station.begin(), station.end(),comp);
		// for (int i = 0; i <= n; ++i)
		// {
		// 	cout<<station[i].dis<<' '<<station[i].price<<endl;
		// }

		double maxrun = davg * cmax;
		double run = 0;		//总路程
		double cost = 0;		//总花费
		double fuel = 0;		//当前剩余油量
		for (int i = 0; i < n; ++i)
		{
			if((station[i+1].dis - station[i].dis) > maxrun){		//间距大于加满油能跑的最大距离
				printf("The maximum travel distance = %.2f\n", run+maxrun);
				break;
			}
			double nearest = i+1;
			double cheapest = i+1;

			for (int j = i+1; j <= n && (station[j].dis - station[i].dis) <= maxrun; ++j)			//只在前n个加油站中找最近比当前便宜的的加油站
			{
				//找整个阶段最便宜的加油站必须放在前面，如果放在后面cheapest可能来不及更新进入错误的分支
				if(station[j].price <= station[cheapest].price){		//如果都大于当前价格，找到较便宜的且尽量走得更远
					cheapest = j;
				}
				if((station[j].price <= station[i].price)){		//有比当前更便宜的加油站
					nearest = j;
					break;
				}
			}

			if(station[cheapest].price > station[i].price){	//都比当前的油价贵
				cost += station[i].price * (cmax - fuel);	//先加满
				fuel = cmax;
				run += station[cheapest].dis - station[i].dis;	//跑的路程
				fuel -= (station[cheapest].dis - station[i].dis)/davg;	//跑到下一个站消耗的油量
				i = cheapest-1;									//循环会再+1，所以先-1
			}else{											//比当前便宜
				if(fuel * davg < (station[nearest].dis - station[i].dis)){	//如果剩余的油不能跑到下一站
					cost += station[i].price * ((station[nearest].dis - station[i].dis)/davg - fuel);	//加油到能跑到下一站（因为下一站便宜所以尽量到下一站再加）
					fuel = (station[nearest].dis - station[i].dis)/davg;
				}
				//能够跑到下一站(>=)
				fuel -= (station[nearest].dis - station[i].dis)/davg;		//减去到下一站消耗的油量
				run += (station[nearest].dis - station[i].dis);				//加路程
				i = nearest - 1;
			}
		}
		if(run == d)		//只有到达终点站才输出
			printf("%.2f\n", cost);
	}
	return 0;
}