LCP 20-快速公交

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:28 2023-09-13 16:06:28 Updated    

小扣打算去秋日市集，由于游客较多，小扣的移动速度受到了人流影响： - 小扣从 x 号站点移动至 x + 1 号站点需要花费的时间为 inc；
- 小扣从 x 号站点移动至 x - 1 号站点需要花费的时间为 dec。 现有 m 辆公交车，编号为 0 到
m-1。小扣也可以通过搭乘编号为 i 的公交车，从 x 号站点移动至 jump[i]*x 号站点，耗时仅为
cost[i]。小扣可以搭乘任意编号的公交车且搭乘公交次数不限。 假定小扣起始站点记作 0，秋日市集站点记作
target，请返回小扣抵达秋日市集最少需要花费多少时间。由于数字较大，最终答案需要对 1000000007 (1e9 + 7) 取模。
注意：小扣可在移动过程中到达编号大于 target 的站点。 示例 1： >输入：target = 31, inc = 5, dec = 3, jump = [6], cost = [10] > >输出：33 > >解释： >小扣步行至 1 号站点，花费时间为 5； >小扣从 1 号站台搭乘
0 号公交至 6 * 1 = 6 站台，花费时间为 10； >小扣从 6 号站台步行至 5 号站台，花费时间为 3； >小扣从 5 号站台搭乘 0 号公交至
6 * 5 = 30 站台，花费时间为 10； >小扣从 30 号站台步行至 31 号站台，花费时间为 5； >最终小扣花费总时间为 33。 示例
2： >输入：target = 612, inc = 4, dec = 5, jump = [3,6,8,11,5,10,4], cost = [4,7,6,3,7,6,4] > >输出：26 > >解释： >小扣步行至 1 号站点，花费时间为 4； >小扣从 1 号站台搭乘 0 号公交至 3

  • 1 = 3 站台，花费时间为 4； >小扣从 3 号站台搭乘 3 号公交至 11 * 3 = 33 站台，花费时间为 3； >小扣从 33 号站台步行至
    34 站台，花费时间为 4； >小扣从 34 号站台搭乘 0 号公交至 3 * 34 = 102 站台，花费时间为 4； >小扣从 102 号站台搭乘 1
    号公交至 6 * 102 = 612 站台，花费时间为 7； >最终小扣花费总时间为 26。 提示： - 1 <= target <= 10^9 - 1 <= jump.length, cost.length <= 10 - 2 <= jump[i] <= 10^6 - 1 <= inc, dec, cost[i] <= 10^6

关注小爱老师的算法课堂 ，有新鲜视频题解呀！

题目分析：

本题与LCP 09. 最小跳跃次数 的区别在于，最终目标 target 的范围在 [1, 10^9]，所以仅通过正向 BFS 最坏情况下要遍历全部位置，会超时。所以我们考虑反向 BFS，也即从 target 出发，目标是往回走到 0 位置。

特别地，本题在某个位置的不同选择花费的时间均不同，所以需要使用优先队列，而不能使用普通队列存储。

算法细节：

我们在队列中记录两个值：当前花费时间 time 和 当前位置 position（因为优先取较小时间，所以使用声明优先队列时，要声明为小顶堆）。首先将初始值 { target, 0 \ 存入队列。每次从队列中取出头部元素，更新与其相关的位置：

首先，从该位置一站一站移动，到达 0 号站点的时间为 inc \times position，这是因为，我们虽然是反向遍历，但是实际上是从 0 开始向右移动的，所以取 inc 而非 dec。我们提前设置一个全局变量 ans 记录结果，每次更新该值：ans = min(ans, time + inc \times position)，这里不要忘记从 target 到达该位置的时间 time也要被计入。

其次，我们考虑乘坐公交车的情况。遍历所有公交车，有两种情况：

第一种情况是，当前位置 position 刚好处在公交车的某一站上，也即 position\ %\ jump[i] = 0，那么此时该公交车的上一站即为 position \div jump[i]，我们直接将该位置和所需耗时加入队列即可。

第二种情况是，当前位置 position 不在公交车的某一站上，那么可以通过向左走几步或者向右走几步，到达该公交车的某一站，而左边和右边最近的位置可以通过 position\ %\ jump[i] 得到。我们以向左走为例：

当前余数 feed = position\ %\ jump[i]，说明向左走 feed 步，即可到达公交车的某一站 position - feed 号站点。向左走 feed 步的耗时为 inc \times feed，而乘坐一次公交车耗时为 cost[i]，上一站为 (position - feed) \div jump[i]，所以我们将当前拓展出的新节点存入队列即可。

代码：

[]
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
class Solution {
    using ll = long long;
    using PLL = pair<ll, ll>;
    const ll M = 1e9 + 7;
public:
    int busRapidTransit(int target, int inc, int dec, vector<int>& jump, vector<int>& cost) {
        int n = jump.size();

        // 声明小顶堆 优先队列：第一属性为 时间 time，第二属性为 当前位置 position
        priority_queue< PLL, vector<PLL>, greater<PLL> > q;
        // 记录哪些位置已经被遍历过
        unordered_set<ll> seen;

        // 先将 target 存入
        q.emplace(0, (ll)target);
        seen.insert(target);

        // 最坏情况下，从 0 直接前进到 target
        ll ans = (ll)inc * target;

        while(!q.empty()) {
            // 弹出队头元素
            auto [time, position] = q.top();
            q.pop();

            // 若当前时间已经比 全局最优时间 大了，就没必要继续搜索了
            if(time >= ans) continue;
            // 从 target 到 position 时间为 time, 从 position 到 0 为 position * inc
            ans = min(ans, time + position * (ll)inc);

            for(int i = 0; i < n; i++) {
                ll feed = position % (ll)jump[i], next = position / (ll)jump[i];
                if(feed == 0) {
                    // 正好在公交车站
                    if(!seen.count(next)) {
                        q.emplace(time + (ll)cost[i], next);
                    }
                } else {
                    // 向左走到公交车站
                    if(!seen.count(next)) {
                        q.emplace(time + cost[i] + (ll)feed * inc, next);
                    }
                    // 向右走到公交车站
                    if(!seen.count(next + 1)) {
                        q.emplace(time + cost[i] + (ll)(jump[i] - feed) * dec, next + 1);
                    }
                }
            }
        }    

        return ans % M;
    }
};
 Comments
On this page
LCP 20-快速公交
  1. 题目分析：
  2. 算法细节：
  3. 代码：