PAT 甲级 1033. To Fill or Not to Fill (25) C++版

Posted on Edited on In

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

用贪心算法求解
假设增加一个目的地处的加油站，距离为目的地的距离，价格为0，考虑从0距离开始能否到达最后一个加油站的问题
因为先开始没有油，所以如果所有的加油站距离都没有等于0的，那么说明车哪也去不了，直接输出并return
将加油站按照距离dis从小到大排序3.先去第一个加油站，设置变量nowdis表示当前所在的距离，maxdis是能够到达的最大距离，nowprice是当前的站点的价格，totalPrice是总的价格。

reference: https://www.liuchuo.net/archives/2461

case 2 是起点就是终点，这个时候应该是花费为0.00而不是最远距离为0.00
case 4 是终点有加油站，并且这个加油站的价格比较高，这样会导致你加满油达到终点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

struct sta {
    double dis, price;

    sta(int d, double p) {
        dis = d;
        price = p;
    }
};

vector<struct sta> gas;

bool cmp(sta a, sta b) {
    return a.dis < b.dis;
}

int findLower(int cur, int cmax, int davg) {
    for (int i = cur + 1; i < gas.size() && gas[i].dis - gas[cur].dis <= cmax * davg; i++) {
        if (gas[cur].price >= gas[i].price) {
            return i;
        }
    }
    return -1;
}

int findMin(int cur, int cmax, int davg) {
    int inf = 999999, min = 0;
    for (int i = cur + 1; i < gas.size() && gas[i].dis - gas[cur].dis <= cmax * davg; i++) {
        if (gas[i].price < inf) {
            min = i;
            inf = gas[i].price;
        }
    }
    if (inf == 999999) return -1;
    else return min;
}

int main() {
    int n = 0, cur = 0;
    double cmax = 0, d = 0, davg = 0, p = 0, temp = 0, tank = 0, total = 0;
    scanf("%lf %lf %lf %d", &cmax, &d, &davg, &n);

    for (int i = 0; i < n; i++) {
        scanf("%lf %lf", &p, &temp);
        if (temp == d) gas.push_back(sta(temp, 0));
        else gas.push_back(sta(temp, p));
    }

    sort(gas.begin(), gas.end(), cmp);

    if (gas[0].dis != 0) {
        printf("The maximum travel distance = 0.00");
        return 0;
    }

    while (true) {
        int low = findLower(cur, cmax, davg);
        if (low == -1) {
            low = findMin(cur, cmax, davg);
            if (low == -1) {
                break;
            } else {
                total += (cmax - tank) * gas[cur].price;
                tank = cmax - (gas[low].dis - gas[cur].dis) * 1.0 / davg;
            }
        } else {
            if ((gas[low].dis - gas[cur].dis) * 1.0 / davg >= tank) {
                total += gas[cur].price * ((gas[low].dis - gas[cur].dis) * 1.0 / davg - tank);
                tank = 0;
            } else {
                tank -= (gas[low].dis - gas[cur].dis) * 1.0 / davg;
            }
        }
        cur = low;
    }

    if (gas[cur].dis + cmax * davg < d) {
        printf("The maximum travel distance = %.2f", gas[cur].dis + cmax * davg);
    } else {
        printf("%.2f", total + gas[cur].price * ((d - gas[cur].dis) * 1.0 / davg) - tank);
    }
    return 0;
}