0%

PAT 1033：To Fill or Not to Fill 贪心

发表于 分类于 Valine：

加油站问题

题目链接

PAT：https://pintia.cn/problem-sets/994805342720868352/problems/994805458722734080

牛客：https://www.nowcoder.com/practice/f7eba38f7cd24c45982831e0f38518f9?tpId=63&tqId=29602&tPage=2&ru=/kaoyan/retest/9001&qru=/ta/zju-kaoyan/question-ranking

题意

一条线段，起点到终点的距离是D，从起点开始路上有N个加油站，每个加油站的油价都不一样。现在一辆车的油箱容量是Cmax，每单位的油可以跑Davg的路程。现在给定N个加油站各自离起点的距离Di、油价Pi(钱/单位油)。问汽车能否顺利到达终点。如果能，采取怎样的加油策略，花费最少；如果不能，最多能走多少距离。

题解

分析

到达不了终点的情况很好判定：在某两个加油站之间的路程，加满了油也无法通过。此时加满油最多能走的路程+上一个加油站的位置，就是最多能走的距离。

下面考虑在一定能到达情况下，花费最少的策略：

总路程是一定的，每单位的油能跑的路程也是一定的。所以最终使用的油的总量也是定值。直观来看，应该在保证能够继续前行的前提下，在更便宜的加油站加更多的油。

先粗略分析一下，当路过每个加油站的时候，决定是否加油、加多少油的因素有：

  • 首先得保证能在油尽之前到达下一个加油站

  • 其次，如果加油太多，会不会因为前方有更便宜的加油站，导致不划算？

    ===>毕竟如果有更便宜的加油站，到那里留着更大的空间（带着空油箱去）加更多的油，才是更划算的决策

  • 反之，如果加油太少，会不会因为前方可到达的加油站都比较贵，导致不划算？

    ===>为了继续前进，必须到前方可到达的加油站之一进行加油，如果他们都比目前的贵，为何不趁现在多加一点油（加满）？

采用的贪心策略

依据上述的分析，先给出贪心策略（后面证明其正确性）：

  • 到达某个加油站时，检查后面可到达的加油站的范围（加满油可到达的加油站的范围）

  • 若找到了第一个（离当前加油站最近的）价格低于当前加油站价格的加油站st[next]

    • 检查当前的油量
    • 若不够到达st[next]，则加油到刚好到达那个加油站,前往st[next],开始下一轮选择
    • 若够到达，则不加油，直接前往st[next],开始下一轮选择

  • 若每一个可到达的加油站都比当前的贵

    • 检查是否能直接到达终点
    • 若能直接到达终点
      • 检查当前油量是否能到达终点
      • 若能，则直接前往终点
      • 若不能，则加油至正好能到达终点
    • 若不能直接到达终点
      • 在当前加油站加满油
      • 直接前往后面加油站中油价最低的,开始下一轮选择

最优子结构

对子问题进行定义：当前到达第i个加油站，油箱内的剩余油量是gas，求到达终点的最低代价，记做二元组(i, gas)。此最低代价记作S(i, gas)。

对求解每个子问题时候的"选择"进行定义：选择加add的油，下一次前往第j个加油站，记做二元组(add,j)。对于每个子问题(i, gas)，都有一个选择的取值集合\(C\)_\(S(i,gas)\) (Choose_set的简写)，满足选择的合理性（不能超过油箱、加油后能到达所选择的加油站）：

\[ C\_S(i,gas) =\{(add,j)\Big| i \le j, \ \frac {st[j].dist-st[i].dist}{Davg} \le add+gas\le Cmax \} \]

若原问题的解是最优的，那么当做出选择之后，会得到一个子问题，这个的子问题的解一定是最优的。（若不是最优的，则换成最优的，而选择的代价没有改变，进而得到的新的原问题是更优的，与原本的原问题最优的假设矛盾，反证成立）===>最优子结构得证

所以能够得到以下递推式：

\[ S(i,gas)=\min_{(add,j)\in C\_S(i,gas)}\{add\cdot st[i].price + S(j, gas-\frac{st[j].dist-st[i].dist}{Davg}) \} \]

贪心选择性

这个形式化证明起来比较繁琐，这里简要说明（口胡）

  • 当后续加油站有更便宜的

    • 为何要用第一个更便宜的，而不是后面的更便宜的（如果有）
      • 粗证：假设不用第一个，那么需要花更多的油到达后面的，行驶这整个部分的油，都是来自与较高价格的油。而用第一个的话，可以在后续段中使用更低价格的油。
    • 为何要加油至能正好到达：
      • 粗证：假设加更多的油，相当于多加了一部分高价油，而本来这部分油可以被 在到达便宜加油站之后加的油替换掉。因此只需保证能到达这个“第一个更便宜的加油站即可”

  • 如果后续加油站没有更便宜的

    • 若能直接到终点

      • 为何尽量直接到达终点
        • 粗证：既然后面的加油站都比较贵，与其在它们那里停靠加油，不如直接在当前（更便宜的）加油站加满到终点所需的油。

    • 若不能直接到终点：

      • 为何要加满
        • 粗证：为了继续前进，必须在后续加油站的其中一个停靠。最后总得在某个更贵的站点补充油，所以为了能在后续更贵的站点补更少的油，此时应该加得尽可能多。
      • 为何要停在后续最低价的加油站
        • 粗证：为了继续前进，必须在后续加油站的其中一个停靠。既然停靠的话，应该找更便宜的停靠，进而寻找接下来的机会。 (注：我感觉这段证明真的口胡，但没有严谨证明的思路，恳请大家指点)

AC代码

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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include <bits/stdc++.h>

using namespace std;

struct Station {
    double price;
    int dist;
    
    bool operator<(const Station& s){
        return dist < s.dist;
    }
};

Station st[505];

int main() {
    int Cmax, D, Davg, N;
    
    while (~scanf("%d %d %d %d", &Cmax, &D, &Davg, &N)) {
        for (int i = 0; i < N; i++) {
            scanf("%lf %d", &(st[i].price), &(st[i].dist));
        }
        
        sort(st, st + N);
        
        // 第N + 1个加油站为终点
        st[N].price = 0;
        st[N].dist = D;
        
        int loc = 0;   // 当前是第几个加油站
        double gas = 0;   // 当前油量
        double dist = 0;  // 当前行驶距离
        double pay = 0;   // 当前累计付款
        bool ach = true;   // 标记是否能够到达目的地

        if (st[0].dist != 0) { // 第一个加油站不在0位置，一定到不了
            printf("The maximum travel distance = 0.00\n");
            return 0;
        }

        while (loc < N) {
            bool hasNext = false;  // 从当前加油站出去，是否能到达下个加油站
            bool minor = false;    /*当前加油站后面能到达
                                      的所有加油站中，是否有比当前价格低的*/
            double mmin = DBL_MAX; 
            int next = loc;    // 下次加油的加油站序号

            int i = loc + 1;   
            // 开始向后检索当前能够到达的加油站  
            // 最多检查到st[N](终点), 以便最后一个加油站的判定
            while (i <= N && st[i].dist - st[loc].dist <= Cmax * Davg) {
                if (!hasNext) hasNext = true;   // 能进入循环, 代表能继续往后走
                if (i < N){   // 不包括终点
                    // 寻找离当前加油站最近的价格低的加油站
                    if (st[i].price < st[loc].price) {
                        minor = true;   // 标记"有价格比当前低的"
                        next = i;       // 将其设为下一次加油的点
                        break;
                    }
                    // 同时统计所有能到达的加油站中, 价格最低的
                    if (st[i].price < mmin) {
                        mmin = st[i].price;
                        next = i;
                    } 
                }
                i++;
            }

            // 如果当前加油站无法到达任何后续的加油站, 则无法到达终点
            if (!hasNext) {
                ach = false;
                dist += Cmax * Davg; // 这一小段最多行驶这么多
                break;
            }

            // 如果后续可到达的加油站中, 没有比当前价格低的
            if (!minor) {
                // 若直接可以到达终点, 下次就直接到终点
                if (D - st[loc].dist <= Cmax * Davg) {
                    // 如果油不够到终点, 就加到正好够到达终点
                    if (gas * Davg < D - st[loc].dist) {
                        pay += ((double)(D - st[loc].dist) / Davg - gas) * st[loc].price;
                        gas = (double)(D - st[loc].dist) / Davg;
                    }
                    gas -= (double)(st[N].dist - st[loc].dist) / Davg;
                    dist = D;
                    loc = N;
                }
                // 不能到达终点, 就加满油, 然后到达可到的的加油站中价格最低的
                else {
                    pay += (Cmax - gas) * st[loc].price;
                    gas = Cmax;

                    gas -= (double)(st[next].dist - st[loc].dist) / Davg;
                    dist = st[next].dist;
                    loc = next;
                }
            }
            // 有价格低于当前加油站的
            else {
                // 油不够, 就加到正好够到那个加油站
                if (gas * Davg < st[next].dist - st[loc].dist) {
                    pay += ((double)(st[next].dist - st[loc].dist) / Davg  - gas) * st[loc].price;
                    gas = (double)(st[next].dist - st[loc].dist) / Davg;
                }
                
                gas -= (double)(st[next].dist - st[loc].dist) / Davg;
                dist = st[next].dist;
                loc = next;
            }
        }
        
        if (ach) {
            printf("%.2f\n", pay);
        }
        else {
            printf("The maximum travel distance = %.2f\n", dist);
        }
        
    }
    return 0;
}