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

题意

有了高速公路以后，从杭州开车到其他城市变得非常容易。

但是由于汽车的油箱容量有限，我们只能不时的寻找加油站去加油。

不同的加油站的油价可能不同。

你需要计算，到达目的地所花费的最少油钱是多少。

第一行包含四个正整数，Cmax ，油箱的最大容量，D ，杭州到目的地城市的距离，Davg ，每单位汽油可供汽车行驶距离，N ，加油站总数。

接下来 N 行，每行包含一对非负数描述一个加油站的相关信息，Pi ，每单位汽油价格，Di ，该加油站与杭州的距离。

输出到达目的地的最小花费，保留两位 小数。

假设最开始油箱是空的，如果无法到达目的地，则输出 The maximum travel distance = X ，其中 X 是可以行驶的最大距离，保留两位小数。

思路

具体思路如下：

1.先将所有站点信息读入，并按照离起点杭州的距离进行升序排序。

2.从起点出发，枚举起点能到达范围内的所有加油站。

①如果后面有加油站比该站点加油站更便宜，则行驶到该加油站再加油。

②如果没有，则选择一个相对最便宜的加油站，在起点加油站加满油再到这个相对便宜的地方继续考虑。

3.如果无法到达下一个加油站了，则输出能到达的最远距离。

4.通过步骤 2 得到的结果，更新相应的信息，然后重复步骤 2 。

5.如果能到达目的地，则输出到达该目的地的最小花费。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 510;
int c_max, d, d_avg, n;
struct Stop
{
    double p, d;
    bool operator <(const Stop& t)const
    {
        return d < t.d;
    }
}s[N];
int main()
{
    cin >> c_max >> d >> d_avg >> n;
    for (int i = 0; i < n; i++)    cin >> s[i].p >> s[i].d;
    s[n] = { 0,double(d) };
    sort(s, s + n + 1);
    //起点没有加油站
    if (s[0].d)
    {
        cout << "The maximum travel distance = 0.00" << endl;
        return 0;
    }
    double res = 0, oil = 0;
    for (int i = 0; i < n;)
    {
        int k = -1;
        //枚举当前油量可以到达的所有加油站，能到的最远距离为c_max*d_avg
        for (int j = i + 1; j <= n && s[j].d - s[i].d <= c_max * d_avg; j++)
            if (s[j].p < s[i].p)   //找到一个比起点价格低的加油站
            {
                k = j;
                break;
            }
        //或者找到一个不比起点低但在这段范围内价格最低的
            else if (k == -1 || s[j].p < s[k].p)
                k = j;
        //这段这内已经没有加油站了
        if (k == -1)
        {
            printf("The maximum travel distance = %.2lf\n", s[i].d + (double)c_max * d_avg);
            return 0;
        }
        //存在比起点更便宜的加油站，只补充适当的油可以到那儿
        if (s[k].p <= s[i].p)
        {
            res += ((s[k].d - s[i].d) / d_avg - oil) * s[i].p;
            oil = 0;
        }
        else    //此时最优选择时将油箱加满
        {
            res += (c_max - oil) * s[i].p;
            oil = c_max - (s[k].d - s[i].d) / d_avg;
        }
        i = k;
    }
    printf("%.2lf\n", res);
    return 0;
}