PAT 1033 To Fill or Not to Fill

原题链接：1033 To Fill or Not to Fill (25分)

关键词：贪心

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: P​i, 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:

Sample Input 2:

50 1300 12 2
7.10 0
7.00 600
           

Sample Output 2:

题目： 从杭州出发去目的城市，路上有若干加油站，每个加油站的油价不同，你需要计算，到达目的地所花费的最少油钱是多少。

思路：

1. 每次顺次向后搜索加油站，范围是加满油能达到的最远距离之前的所有加油站
2. 找到最近的比当前加油站便宜的加油站，就去最近且便宜的加油
3. 如果到达最远的距离仍旧没有比当前加油站更便宜的加油站，就把油加满，并且下一次停在能到达范围内的加油站中最便宜的加油站
4. 以此类推向后迭代

代码：

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

const int maxn = 510;
double c, dist, dst, davg;	//c容量 dist走的最远距离 dst到终点距离 davg每单位汽油能前进的距离 
int n;	//加油站数 
struct node{
	double p;	//油价 
	int d;	//距离 
}nodes[maxn];

struct cmp_d{	//按距离升序排列 
	bool operator()(const node &a, const node &b){
		return a.d < b.d;	 
	}
};

struct cmp_p{	//按价格升序排列 
    bool operator () (const int a, const int b)
    {
        return nodes[a].p < nodes[b].p;
    }
};

int main(){
	cin >> c >> dst >> davg >> n;
	for(int i = 0; i < n; i ++) cin >> nodes[i].p >> nodes[i].d;
	//把目的地看成距离是dst，油费是0的加油站 
	nodes[n].d = dst;	
	nodes[n].p = 0;	
	sort(nodes, nodes + n + 1, cmp_d());
	
	double max_d = c * davg;	//油箱的油支持的最大距离
	
	bool flag = true;	//是否可达
	double price = 0, peroil;	//花费 当前的油量
	int ne = -1;	//当前站 
	
	for(int i = 0; i < n; i = ne){
		if(nodes[0].d != 0) break;
		
		bool find_cheaper = false;	//是否找到更便宜的
		ne = i + 1;	//初始化下一个加油站
		if(nodes[ne].d - nodes[i].d > max_d){	//下一站无法到达 
			dist = nodes[i].d + max_d;
			ne = i;
			break;
		} 
		
		vector<int> v;
		for(int j = ne; j <= n && (nodes[j].d - nodes[ne].d <= max_d); j ++ ){
			if(nodes[j].p <= nodes[i].p){	//有更便宜的加油站
			 	find_cheaper = true;
			 	ne = j;
			 	break;		
			}
			else v.push_back(j);	//把所有能一次加油走到的加油站加入v 
		}
 		if(!find_cheaper){
 			sort(v.begin(), v.end(), cmp_p());
 			ne = v[0];
			price += (c - peroil) * nodes[i].p;
			double ptr = (nodes[ne].d - nodes[i].d)	/ davg;
			peroil = c - ptr; 
		} 
		else{
            double l = nodes[ne].d - nodes[i].d;
            double ptr = l / davg; // 需要消耗的油量
            if (ptr > peroil) price += (ptr - peroil) * nodes[i].p;
            peroil = 0;
        }
	} 
	
	if (ne == n) printf("%.2lf\n", price);
    else printf("The maximum travel distance = %.2lf\n", dist);
	return 0;
}