想请教下一道面试题

2020-12-02 06:47:06 +08:00
 sextoybie
请教下 共享电动车， 小明和小华住同一街上 相隔 X 米。 从小明到小华的路上 有 n 辆电动车 分别在 p1, p2, ...pn 点上。

每一电动车的电量 不同导致每辆车可走的米数不同，d1, d2, ... dn. (从 P* 点开始算） 小明可以确保的是 每两辆相隔的车，都有充足的电量从上一辆到达下一辆 ， 小华可以确保最靠近小华家的那辆车 有足够的电 量到他家从那点出发.

每辆车都有不同的启动金 C1, C2, ...Cn 和每米的价钱 m1, m2, m3...mn. (就是如果小明 启动 电动车 2 ,骑了 4 米 那么小明就是消费了 C2+ 4 * m2 。

当然每当小明遇到一辆电动车， 小明都选择换骑。
小明家里有一辆电动车了， 小明为他冲电的，所以没有启动费， 它可以让小明骑到 P0 米 以每米 m0 的价格

身为刚毕业的小明 如何最低成本从他家开始出发到小华家 同时必须使用电动车作为工具呢？
3164 次点击
所在节点    程序员
34 条回复
yzbythesea
2020-12-02 07:25:11 +08:00
这图是个 DAG ？这不是拓扑排序吗？
Herobs
2020-12-02 07:27:32 +08:00
动态规划，状态是每一辆选择骑或者不骑。
sextoybie
2020-12-02 07:31:17 +08:00
@yzbythesea 是的，DAG. 该如何跑呢？
sextoybie
2020-12-02 07:34:13 +08:00
当然每当小明遇到一辆电动车， 小明都选择换骑。
改为
当然每当小明遇到一辆电动车， 小明都可以选择换骑。
sextoybie
2020-12-02 07:35:57 +08:00
@Herobs 可以说的详细点吗？ 是的 基本的理解题目 和需要 都明白点， 就是写不出来。
dartabe
2020-12-02 07:46:19 +08:00
好简单的动态规划 如果我没理解错

当前价格 = 到达前一点的最低价格 + min(所有可用的车从前一点到当前一点的价格)
dartabe
2020-12-02 07:51:41 +08:00
我错了 好像不对
dartabe
2020-12-02 07:53:34 +08:00
可能是 dfs 直接算
sextoybie
2020-12-02 07:55:18 +08:00
@dartabe dfs 直接算 不能吧， 需要动态规划（吧）
dartabe
2020-12-02 07:57:21 +08:00
@sextoybie 动规好像不行 前面的选择会影响后面的状态
dartabe
2020-12-02 08:02:58 +08:00
类似于 leetcode 全排列 截止条件不一样 当然我就 leetcode 100 题水平 高手来看下
sextoybie
2020-12-02 08:05:11 +08:00
@dartabe 动态规划 是可以的, 面试时的提示。还是谢谢大佬的点击和分享
yzbythesea
2020-12-02 08:08:30 +08:00
@sextoybie DFS 可以吧，只是比较笨。

先拓扑排序，然后必经点得选，凡非必经点儿之间，选最短的组合。

当然我现在觉得这可能不是一个 DAG，那你也可以用 Dijkstra 做
yzbythesea
2020-12-02 08:09:19 +08:00
好奇下这是哪家的面试题，难度有点爆炸。
youngzy
2020-12-02 08:24:42 +08:00
记录到每个节点时的最小花费，用到当前节点的花费更新后续可到达节点的最小花费。最终结果即为最终节点记录的最小花费。
sextoybie
2020-12-02 08:27:08 +08:00
@youngzy 嗯 也是这样想的， 就是需要先跑 DP 算出到每个节点时的最小花费。 然后当图是 DAG， 在跑一次？
xuanbg
2020-12-02 08:31:53 +08:00
小明能够确保的是每两辆相隔的车，都有充足的电量从上一辆到达下一辆 ，所以必须选择换骑啊。最低成本有得选吗？无非就是自己家里的车尽量骑远一点呗。
sextoybie
2020-12-02 08:37:59 +08:00
@xuanbg 小明能够确保的是 上辆车至少有足够电量到下辆车， 是否能到下下辆 / 下下下辆 因车而异。
futou
2020-12-02 08:41:41 +08:00
如果我没理解错的话，题目指的是车可以从 p1 骑到 p2 或 p3，以此类推。p0 貌似一定要骑到 p1，不过无论怎样不影响解题。
如果是这样的话，这种结构太简单了都用不上 DAG...

if 终点是奇数
遍历计算两个相邻奇数点之间的最短路径
求和
else
1. 同奇数处理，然后奇数最短路径+最后一段距离
2. 判断相邻偶数点两两最短路径+p1 到 p2 距离
比较 1. 2.取最短
ilunny
2020-12-02 08:41:45 +08:00
感觉有点像路由寻址

这是一个专为移动设备优化的页面（即为了让你能够在 Google 搜索结果里秒开这个页面），如果你希望参与 V2EX 社区的讨论，你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/731200

V2EX 是创意工作者们的社区，是一个分享自己正在做的有趣事物、交流想法，可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX