题解 | #To Fill or Not to Fill#

纸算很清晰但写代码很绕的一道题 建议花两分钟纸算一下样例 遇到比当前便宜的直接切 只能遇到贵的的话得把当前价格的油走满，并在这途中选一个除自己之外的最便宜的油加满

#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>

using namespace std;

class station{
public:
	double price;
	double location;
	station(double p, double l):price(p),location(l){}
	bool operator<(const station &b) const {
		return location < b.location;
	}
};

vector<station> v;

int main(){
	double Cmax,dist,Davg,n;
	while(scanf("%lf%lf%lf%lf",&Cmax,&dist,&Davg,&n) != EOF){
		double price,location;
		for(int i=0; i<n; i++){
			scanf("%lf%lf",&price, &location);
			v.push_back(station(price, location));
		}
		sort(v.begin(),v.end());
		double ans = 0;
		double left = 0;
		int last = 0;
		double farthest = Cmax * Davg + left;
		int next = 1;
		bool back = false;
		bool gg = false;
		int nextmax;
		//有个细节 用back回去的时候 应该是便宜的油能走多远走多远 这也令v[last].location和left存在了巨大差别 
		while(1){
			if(v[next].price <= v[last].price && v[next].location <= farthest && v[next].location >= v[last].location && !back){//可坚持到这个更便宜的可行的加油站 
				ans += (v[next].location - left)*v[last].price/Davg;
				left = v[next].location;
				farthest = Cmax * Davg + v[next].location;
				last = next;
				if(farthest > dist){
					farthest = dist;
				}
				next++;
			}else if(v[next].location > farthest && !back){//发现过头了，必须接受一个更贵的加油站 那得找前面跳过过的当中最便宜的 
				back = true;
				nextmax = next;
				next = last + 1;
				if(next == nextmax){
					gg = true;
				}
			}else if(back){
				double minprice = v[next].price;
				int minnext = next;
				while(next < nextmax){
					if(v[next].price < minprice){
						minprice = v[next].price;
						minnext = next;
					}
					next++;
				}//得到了minnext以及minprice
				next = minnext;
				ans += (farthest - left)*v[last].price/Davg;
				left = farthest;
				farthest = Cmax * Davg + v[next].location;
				last = next;
				if(farthest > dist){
					farthest = dist;
				}
				next++;
				back = false;
			}else{
				next++;
			}
			if(next == v.size() || gg){//没有能换的了
				if(farthest < dist){
					printf("The maximum travel distance = %.2lf\n",farthest);
				}else{
					ans += (dist - left)*v[last].price/Davg;
					printf("%.2lf\n",ans);
				}
				break;
			}
		}
		v.clear();
	}
	return 0;
}