This is an after class programming problem of ads. The main algorithm used is Greedy Algorithm

Description

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:

1
2
3
4
5
6
7
8
9
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:

1
749.17

Sample Input 2:

1
2
3
50 1300 12 2
7.10 0
7.00 600

Sample Output 2:

1
The maximum travel distance = 1200.00

Solution

Just saw this problem, my idea is: finding the cheapest gas station within the driving distance, then refuel to make sure it can just reach the next gas station until the end.

But in fact, the optimal solution should be to find the cheapest gas station within the mileage range to add the most fuel, and then go to the next gas station to replenish it, so as to ensure that it can just reach the terminal.

So, the answer will be:

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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
//
//  main.cpp
//  test
//
//  Created by Yy Y on 2021/5/19.
//

#include <iostream>
#include <iomanip>
#include <cstring>
#include <algorithm>
using namespace std;

/* 加油站结构体 */
struct station
{
    double price;
    int dis;
};
typedef struct station gas_station;

/* 使结构体按油价从低到高排序 */
bool cmp_price(gas_station a, gas_station b)
{
    return a.price < b.price;
}

/* 贪心算法核心 */
double Greedy(gas_station arr[], int map[], int max_dis, int num_station, int distance, int per)
{
    /* 加油最远需要行驶到距离：1.加满 2.加到刚好到终点 */
  	int wait2go;
    double sum = 0;
    for(int i=0; i<num_station; i++)
    {
        /* 从该加油站加满也到不了终点的情况，则最多走max_dis */
      	if(arr[i].dis + max_dis <= distance)
            wait2go = max_dis;
      	/* 能到终点的情况，最远走distance - arr[i].dis */
        else
            wait2go = distance - arr[i].dis;
      	/* 记录这次加油真正需要走的距离 */
        int cnt=0;
        for(int j=arr[i].dis; j<arr[i].dis+wait2go; j++)
        {
            /* 如果没走过就记录在内 */
          	if(map[j] == 0)
            {
                map[j] = 1;
                cnt++;
            }
        }
      	/* 计算价格 */
        sum += cnt * arr[i].price / per;
    }
    return sum;
}

/* 检查能不能走到底 */
bool Check(int map[], int distance)
{
    int i = 0;
    while (i < distance)
    {
        /* 如果有没走到的地方，说明无法成功走到 */
      	if(map[i] == 0)
        {
            cout << "The maximum travel distance = " << fixed << setprecision(2) << (double)i << endl;
            return 0;
        }
        i++;
    }
    return 1;
}

/* 主函数 */
int main(int argc, const char * argv[])
{
    /* 读入油箱容量、距离、每公里油耗、加油站数量 */
    int capcity, distance, per, num_station;
    cin >> capcity >> distance >> per >> num_station;
    /* 加满油箱能行驶到最远距离 */
    int max_dis = capcity * per;
    
    /* 读入加油站信息 */
    gas_station arr[num_station];
    for(int i=0; i<num_station; i++)
    {
        cin >> arr[i].price >> arr[i].dis;
    }
    /* 对加油站按油价从低到高排序 */
    sort(arr, arr+num_station, cmp_price);
    
    /* 记录有没有走过 */
    int map[distance];
    memset(map, 0, sizeof(map));
    /* 贪心求费用 */
    double sum = Greedy(arr, map, max_dis, num_station, distance, per);
    /* 如果能走到目的地，输出费用 */
    if(Check(map, distance))
        cout << fixed << setprecision(2) << sum << endl;
    
    return 0;
}