想请教下一道面试题

[sextoybie]

请教下 共享电动车， 小明和小华住同一街上 相隔 X 米。 从小明到小华的路上 有 n 辆电动车 分别在 p1, p2, ...pn 点上。

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

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

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

身为刚毕业的小明 如何最低成本从他家开始出发到小华家 同时必须使用电动车作为工具呢？

[xuanbg]

这题目命题不够明确，没说小明到小华家不是一条路。。。真是令人头秃

每个相邻点都相同，只是代价不同。这不就是求最短路径吗？ A*算法就是最简单的实现了。

[xuanbg]

@sextoybie 当然每当小明遇到一辆电动车， 小明都选择换骑。 这是题目里面的。

[futou]

#19 回复完看到了#18 补充信息 2333，参照#15 吧

[xuanbg]

@xuanbg 这题目命题不够明确，没说小明到小华家不是一条路。。。真是令人头秃

每个相邻点都相通，只是代价不同。这不就是变相的求最短路径吗？两点间的代价就是启动费+里程费，这个代价等同距离。A*算法就是最简单的实现了。

[misdake]

骑到 i 点下车的最小代价 cost[i] = min { cost[j] + 骑 j 车到 i 点的代价 }，j 从电量骑到 i 点的车里选，把每个点选择的 j 存下来最后反查

[hejw19970413]

贪心就可以

[youngzy]

@sextoybie
可以在 dp 的时候同时记录转移到该节点的节点编号（也就是当前的最优解是从哪个节点转移过来的），这样在 dp 结束的时候你就有了一个反向的路径链，有需要的话可以进一步处理

[zifangsky]

先假设从 P(m) 到其后的某一个点 P(n) 都可以连通，画出一个有向无环图，然后根据「不同导致每辆车可走的米数不同」中的 d1 d2 ... dn 把不可行的边去掉，最后就变成求 最短路问题 了（其中每个边的边长由 C1 C2 ... Cn 和 m1 m2 ... mn 确定）

[yazoox]

这个题目有难度，有意思。学习一下。
看看有没有大神帖代码出来。

[dartabe]

我又想了下 dp 可以做 不过要维护一个 dp 数组就可以了

j = 车辆数目
dp 数据长度 j
从尾到头遍历所有车:
dp[当前地点] = min(当前车能到达的所有点 + dp[当前车能到达的所有点])

[jsun]

动态规划，先维护一个二维数组表示能到达该点电动车，例如能骑到 P6 的是 P3 和 P5，则 A[6]=[3,5]。然后列 dp 公式，dp[6]=Min((P6-P5)*m5+C5+dp[5],(P6-P3)*m3+C3+dp[3]) 。dp[n]=遍历 A[n],求最小值 min

[newtype0092]

有 test case 么？有点思路但是还需要调试一下，上面几位的解法也不太好验证。

[hitmanx]

@jsun 我的思路和你一样。

[shunconf]

由于要换车，小明选择公交车直达