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

  greedy ：

Treat destination as the third n One site , The price for 0;

Sort all sites by distance ;

Search for the site with the lowest price in the maximum mileage range of the current site ：1） If you encounter a site with a lower price than the current site, go immediately （ Maybe it's not the lowest in the mileage range , But it costs less to do so than to find the lowest in the mileage range and go , Because sites are sorted by distance , According to the greedy algorithm , Consider only the current small scope , Ensure that the cost of each step is minimal , That is to say, one step can be saved ）;2） If the price is higher than the current site, it is to find the smallest ;

If k==-1 It means that no station can be reached within the current mileage range , immediate withdrawal while loop , Output the current site distance + Maximum mileage ;

The next step is to calculate how much oil to add to the next station ：1） If the next site is cheaper than the current site , Then add the oil just enough to reach the next station ;2） If not , Fill up the current site , This will ensure that at least the oil used before arriving at the next station is the cheapest （ greedy , Consider only the current small range ）;

Pay attention to updating the current fuel volume and cost .

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

int now;// Current site 
double limit;// Maximum range 
double nowc;// Current oil volume 
struct Station {
	double p;// Unit price 
	double dis;// distance 
} 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; // The lowest price 
		int j = -1; // The lowest price corresponds to the site 
		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;// Find a gas station with a lower price than the current one , Go to immediately 
				}
			}
		}
		if (j == -1) {
			break;// Cannot reach 
		}
		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;
}