我正在做一些编程练习。这个问题已经广为人知，并在不同的地方得到了回答。
FrogRiverOne 求 Frog 最早能跳到河对岸的时间。 https://codility.com/programmers/task/frog_river_one/
我的问题是，如果 Frog 可以跳 D 的距离怎么办？我们怎样才能找到最短的过河时间，具有最好的运行时间复杂度？谢谢!
int solution(int X, vector<int> &A, int D); // frog can jumps from 1 to D steps
最佳答案
我认为shole的贪心解法几乎是正确的。如果在更改 Current_Pos 时包含递归传播步骤，您将确保 Frog 始终位于最前面的位置。
这是避免递归的替代方法:
如果有叶子，则使用一个占用数组为每个位置存储。并为每个位置使用带有节点的 union 查找数据结构。 union-find 数据结构将跟踪可以相互到达的节点(即连接的组件)。接下来的任务是找到两个河岸相连的第一个时间点。
要找到它，请执行以下操作:每次新叶子开始事件时，将其位置标记为已占用。然后，将 union-find 数据结构中的节点与从该位置可达的所有其他占用节点 union 起来(-D 到 +D)。最后，检查两个河岸是否相连。总体时间复杂度为 O(ND+X)。
两种解决方案中哪一种更快取决于输入。
关于c++ - 增强型 FrogRiverN，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/38237007/