题解 | #To Fill or Not to Fill#

//土尔逊Torson 编写于2023/06/01
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <string>
#include <stdlib.h>
#include <vector>

using namespace std;

struct GasStation {
	double Pi; // the unit gas price
	double Di; // the distance between this station and Hangzhou
};

struct CarAndGoal {
	int Cmax; // the maximum capacity of the tank
	int D; // the distance between Hangzhou and the destination city
	int Davg;// the average distance per unit gas that the car can run
	double MT; // the maximum travel distance
	double CT; // the cheapest total price
	int D_now; // car current station position
	double remain_oil; // remain oil
};

// ranking gas station vector from low distance to long distance
// in the same distance ranking the gas station from low price to high price
bool cmp092(GasStation a, GasStation b) {
	if (a.Di == b.Di) {
		return a.Pi < b.Pi;
	}
	else {
		return a.Di < b.Di;
	}
}

void GetGoCar(CarAndGoal &car7, vector<GasStation> &GS, int n) {
	int CarMax = car7.Cmax*car7.Davg; // the maximum distance car can run with full tank of oil
	car7.D_now = 0;
	car7.remain_oil = 0;
	car7.MT = 0;
	car7.CT = 0;
	int minCar; // car in the traversal process
	if (GS[0].Di != 0) {
		car7.MT = 0;
		car7.CT = 0;
	}
	else {
		while (1) { // use break as condition to stop while loop
			if (car7.D_now + 1 == n) { 
				break; // if next station is the last then stop
			}
			minCar = car7.D_now + 1; // the current in distance reachable most cheap station
			int i, tag = 0;
			// pick station
			for (i = car7.D_now + 1; i < n; ++i) {
				// if the distance from current station to next station longer than 
				// the distance car maximum can go, then it is unreachable
				if (GS[i].Di - GS[car7.D_now].Di > CarMax) {
					break;
				}
				if (GS[i].Pi < GS[car7.D_now].Pi) { // if have cheaper station then goto that
					minCar = i; // the station index is been stored
					tag = 1; // tag that information
					break;
				}
				if (GS[i].Pi < GS[car7.D_now].Pi) {
					minCar = i; // if didn't show up the cheaper station then this is next station
				}
			}
			// update
			if (tag) { // if have lower price station, then goto this station to fill the tank
				double require_oil = (GS[minCar].Di - GS[car7.D_now].Di) / car7.Davg;
				if (require_oil > car7.remain_oil) {// needed oil > remain oil
					car7.CT += (require_oil - car7.remain_oil)*GS[car7.D_now].Pi;
					car7.remain_oil = require_oil;
				}
				car7.remain_oil -= require_oil;
				car7.D_now = minCar;
			}
			else { // if didn't have cheaper station
				if (i == car7.D_now + 1) {// if can't goto next station
					break;
				}
				else if (car7.D - GS[car7.D_now].Di < CarMax) {
					break; // current station can goto terminal and didn't have cheaper station
				}
				// fill the tank full in the current station and then goto the most lower price station, which is the index mincar
				car7.CT += (car7.Cmax - car7.remain_oil)*GS[car7.D_now].Pi;
				car7.remain_oil = car7.Cmax - (GS[minCar].Di - GS[car7.D_now].Di) / car7.Davg;
				car7.D_now = minCar;
			}
		}
		if (car7.D - GS[car7.D_now].Di > CarMax) {
			car7.MT = GS[car7.D_now].Di + CarMax;
		}
		else {
			car7.MT = car7.D;
			double require_oil = (car7.D - GS[car7.D_now].Di) / car7.Davg;
			if (require_oil > car7.remain_oil) {
				car7.CT += (require_oil - car7.remain_oil)*GS[car7.D_now].Pi;
			}
		}
	}
}

int main() {
	CarAndGoal car;
	int n;
	while (scanf("%d%d%d%d", &car.Cmax, &car.D, &car.Davg, &n) != EOF) { // get the car data
		vector<GasStation> GS;
		for (int i = 0; i < n; ++i) { // get the gas station status
			GasStation tmp;
			scanf("%lf%lf", &tmp.Pi, &tmp.Di);
			GS.push_back(tmp);
		}
		// ranking gas station vector from low distance to long distance
		// in the same distance ranking the gas station from low price to high price
		sort(GS.begin(), GS.end(), cmp092);
		GetGoCar(car, GS, n);
		// output the final answer
		if (car.MT < car.D) {
			printf("The maximum travel distance = %.2f\n", car.MT);
		}
		else {
			printf("%.2f\n", car.CT);
		}
	}
	system("pause");
	return EXIT_SUCCESS;
}
//64 位输出请用 printf("%lld")