【PAT刷题】 To Fill or Not to Fill

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: C​max​​ (≤ 100), the maximum capacity of the tank; D (≤30000), the distance between Hangzhou and the destination city; D​avg​​ (≤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 D​i​​ (≤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

思路

区间贪心。使用油箱容量乘以每单位油能跑的距离可以得到一个区间。在每个加油站向前看这个区间的长度，每次都找出离油费比此加油站少并且离此加油站最近的加油站。算出到这一个加油站的油费，并实时更新当前位置与当前油箱中的容量。

若当前加油站就是区间内最便宜的加油站，则在此加油站把油箱加满。

若当前加油站到下一个相邻的加油站的距离大于区间，则不能到达，直接输出最小距离。

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef struct {
	double price;
	double dis;
} jiayouzhan;
bool compare(jiayouzhan a, jiayouzhan b)
{
	if (a.dis == b.dis)
	{
		return a.price < b.price;
	}
	else
	{
		return a.dis < b.dis;//从小到大排；
	}
}
int main()
{
	double c, d, g;//c为油箱容量，d为两地之间的距离，g为每单位的油可以跑的距离，n为期间加油站的数量
	int n;
	while (cin >> c >> d >> g >> n)
	{
		jiayouzhan A[501];
		double qujian = g * c;
		int i, j;
		bool flag;
		double sumprice, nowgas;
		double arr;
		for (i = 0;i < n;i++)
		{
			cin >> A[i].price >> A[i].dis;
		}
		A[n].price = 0;
		A[n].dis = d;
		sort(A, A + n + 1, compare);
		if (A[0].dis != 0)//如果没有距离为0的加油站，则根本不能出发。
		{
			cout << "The maximum travel distance = 0.00" << endl;
			continue;
		}
		sumprice = 0;
		nowgas = 0;
		flag = false;
		for (i = 0;i < n;)
		{
			if (A[i + 1].dis - A[i].dis > qujian)//不能走到下一个站
			{
				arr = A[i].dis + qujian;
				printf("The maximum travel distance = %.2f\n", arr);
				flag = true;
				break;
			}
			int tag = i;
			double minprice =A[i].price ;
			for (j = i;A[j].dis <= A[i].dis + qujian;j++)//找出当前站向前区间内的比这个油费少的最近的站
			{
				if (A[j].price < minprice)
				{
					tag = j;
					minprice = A[j].price;
					break;
				}
			}
			if (tag != i)
			{
				double delta = (A[tag].dis - A[i].dis) / g;
				if (nowgas >= delta)//当前油箱内的油可以到下个加油站，不需要加油
				{
					i = tag;
					nowgas -= delta;
				}
				else//当前油箱内的油不可以到加油站，要加油
				{
					sumprice += (delta - nowgas)*A[i].price;
					i = tag;
					nowgas = 0;
				}
			}
			else//找不到，表明此加油站是当前区间内最便宜的加油站，则加满油
			{
				sumprice += (c - nowgas) * A[i].price;
				nowgas = c - (A[i + 1].dis - A[i].dis) / g;
				i++;
			}
		}
		if (flag)
		{
			continue;
		}
		printf("%.2f\n", sumprice);
	}
	return 0;
}