快速公交

LCP 20. 快速公交

小扣打算去秋日市集，由于游客较多，小扣的移动速度受到了人流影响：

小扣从 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

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: int busRapidTransit(int target, int inc, int dec, vector<int>& jump, vector<int>& cost) { } };

golang 解法, 执行用时: 24 ms, 内存消耗: 11.8 MB, 提交时间: 2023-10-25 23:48:52

type Pos struct {
	//从当前站点到达 target 站点所需的最小时间为 cost
	id, cost int
}

func busRapidTransit(target int, inc int, dec int, jump []int, cost []int) int {
	const mod = int(1e9) + 7
	h := &Heap{slice: []Pos{{id: target, cost: 0}}}
	for h.Len() > 0 {
		cur := h.pop()
		if cur.id == 0 {
			return cur.cost % mod
		}
		h.push(Pos{id: 0, cost: cur.cost + inc*cur.id})
		for i, v := range jump {
			x := cur.id / v
			dest := x * v
			h.push(Pos{id: x, cost: cost[i] + cur.cost + inc*(cur.id-dest)})
			if dest < cur.id {
				dest = (x + 1) * v
				h.push(Pos{id: x + 1, cost: cost[i] + cur.cost + dec*(dest-cur.id)})
			}
		}
	}
	return 0
}

type Heap struct {
	slice []Pos
}

func (h *Heap) Len() int           { return len(h.slice) }
func (h *Heap) Less(i, j int) bool { return h.slice[i].cost < h.slice[j].cost }
func (h *Heap) Swap(i, j int)      { h.slice[i], h.slice[j] = h.slice[j], h.slice[i] }
func (h *Heap) Push(x interface{}) { h.slice = append(h.slice, x.(Pos)) }
func (h *Heap) Pop() interface{} {
	res := h.slice[h.Len()-1]
	h.slice = h.slice[:h.Len()-1]
	return res
}
func (h *Heap) push(p Pos) { heap.Push(h, p) }
func (h *Heap) pop() Pos   { return heap.Pop(h).(Pos) }

golang 解法, 执行用时: 8 ms, 内存消耗: 3.6 MB, 提交时间: 2023-10-25 23:48:44

func busRapidTransit(target int, inc int, dec int, jump []int, cost []int) int {
	const mod = int(1e9) + 7
	memo := map[int]int{}
	// 返回从起点 0 到达 end 站点所需最小时间
	var help func(end int) int
	help = func(end int) int {
		if end == 0 {
			return 0
		}
		// 从 0 站坐公交会回到原点，是无用功，肯定要步行
		if end == 1 {
			return inc
		}
		if res, ok := memo[end]; ok {
			return res
		}
		res := end * inc // 先假设全靠步行
		// 最后一步尝试坐每一辆公交
		for i, v := range jump {
			x := end / v
			// 从 x 站点坐公交达到的站点
			dest := x * v
			if dest == end { // end 可以整除 v
				res = min(res, cost[i]+help(x))
			} else {
				// 即 end 不能整除 v
				res = min(res, cost[i]+help(x)+inc*(end-dest))
				// 尝试从 x+1 坐公交之后步行返回的方案
				dest = (x + 1) * v
				res = min(res, cost[i]+help(x+1)+dec*(dest-end))
			}
		}
		memo[end] = res
		return res
	}
	return help(target) % mod
}

java 解法, 执行用时: 12 ms, 内存消耗: 42.6 MB, 提交时间: 2023-10-25 23:47:39

class Solution {
    final int MOD = (int) 1e9 + 7;
    Map<Long, Long> map = new HashMap<>();
    int[] jump, cost;
    int inc, dec;
    public int busRapidTransit(int target, int inc, int dec, int[] jump, int[] cost) {
        this.cost = cost; this.jump = jump;
        this.inc = inc; this.dec = dec;
        return (int)(dfs(target) % MOD);
    }
    private long dfs(long n) {
        if(n == 0) return 0;
        if(n == 1) return inc;
        if(map.containsKey(n)) return map.get(n);
        long ans = n * inc;
        for(int i=0; i<jump.length; i++) {
            long reminder = n % jump[i];
            if(reminder == 0) {
                ans = Math.min(ans, dfs(n/jump[i]) + cost[i]);
            } else {
                ans = Math.min(ans, dfs(n / jump[i]) + cost[i] + reminder * inc);
                ans = Math.min(ans, dfs(n / jump[i] + 1) + cost[i] + (jump[i] - reminder) * dec);
            }
        }
        map.put(n, ans);
        return ans;
    }


}

java 解法, 执行用时: 7 ms, 内存消耗: 40.3 MB, 提交时间: 2023-10-25 23:47:19

class Solution {
    final int MOD = (int) 1e9 + 7;
    public int busRapidTransit(int target, int inc, int dec, int[] jump, int[] cost) {
        int n = jump.length;

        PriorityQueue<Node> pq = new PriorityQueue<>((o1, o2) -> (int) ((o1.cost - o2.cost) % MOD));
        pq.offer(new Node(0, target));

        HashSet<Integer> visit = new HashSet<>();
        long res = (long)target * inc;

        while (!pq.isEmpty()) {
            Node cur = pq.poll();
            if (visit.contains(cur.pos)) continue;
            visit.add(cur.pos);

            res = Math.min(res, cur.cost + (long)cur.pos * inc);
            if (cur.pos == 1) break;
            
            pq.offer(new Node(cur.cost + (long)(cur.pos - 1) * inc, 1));
            for (int i = 0; i < n; i++) {
                long remainder = cur.pos % jump[i];
                int prev = cur.pos / jump[i];
                if (remainder == 0) {
                    pq.offer(new Node(cur.cost + cost[i], prev));
                } else {
                    pq.offer(new Node(cur.cost + cost[i] + remainder * inc, prev));
                    pq.offer(new Node(cur.cost + cost[i] + (jump[i] - remainder) * dec, prev + 1));
                }
            }
        }
        return (int)(res % MOD);
    }
    class Node {
        long cost;
        int pos;

        public Node (long cost, int pos) {
            this.cost = cost;
            this.pos = pos;
        }
    }
}

cpp 解法, 执行用时: 116 ms, 内存消耗: 21.4 MB, 提交时间: 2023-10-25 23:46:54

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;
    }
};

python3 解法, 执行用时: 128 ms, 内存消耗: 17.5 MB, 提交时间: 2023-10-25 23:46:35

from functools import lru_cache

class Solution:
    def busRapidTransit(self, target: int, inc: int, dec: int, jump: List[int], cost: List[int]) -> int:
        @lru_cache(None)
        def search(num):
            if num == 0:
                return 0
            result = num * inc
            for i in range(len(jump)):
                last, left = num // jump[i], num % jump[i]
                result = min(result, search(last) + cost[i] + inc * left)
                if num > 1 and left > 0:
                    result = min(result, search(last + 1) + cost[i] + dec * (jump[i] - left))
            return result

        return search(target) % 1000000007

python3 解法, 执行用时: 156 ms, 内存消耗: 17.3 MB, 提交时间: 2023-10-25 23:46:06

class Solution:
    def busRapidTransit(self, target: int, inc: int, dec: int, jump: List[int], cost: List[int]) -> int:
        #自底向上记忆化递推   
        memo = dict() #记忆字典
        
        def findroute(cur_target: int) -> int:  
            if cur_target == 0:     #当前站点已经是0了返回0代价
                return 0
            if cur_target in memo:
                return memo[cur_target]
            mincost = cur_target*inc  #最小代价初始化为直接回终点站，我相信这种情况应该存在

            for i,val in enumerate(jump): #遍历附近的公交站点
                if cur_target>1:#至少得大于1，不然我自己走了还坐个屁公交
                    if cur_target%val==0: #当前站能够坐公交
                        mincost =min(mincost,cost[i]+findroute(cur_target//val)) #递归下一站
                    else:
                        bias = cur_target%val #当前站不能做公交看看需要走几步到达公交站  
                        if cur_target-bias>0: #往前走几步如果没到终点，就该坐公交，递归下一站
                            mincost=min(mincost,bias*inc+cost[i]+findroute(cur_target//val))

                        mincost = min(mincost,(val-bias)*dec+cost[i]+findroute(cur_target//val+1))#往后走几步坐公交递归下一站
            memo[cur_target]=mincost
            return mincost

        return findroute(target)%(1000000007)

上一题

下一题

详情