给定一个包含 N 个元素的数组,编号从 1 到 N。第 i 个元素的值为 V[i]。此外,所有元素都是不同的。
要从第 i 个元素移动到第 j 个元素,我们需要花费 |i-j| 的成本。 但只有在以下情况下,我们才能从第 i 个元素跳到第 j 个元素:
j 与键 i 的距离不小于 K 个位置(即 j 不应在 [ i-K+1, i+K-1 ] 范围内)。
V[j] < V[i].
每个元素可能有0个或多个可以跳转到的元素。
我们需要找到从每个元素 i 到可以在它之后跳转的最近元素所需的成本总和。如果对于元素 i 没有可以跳转到的下一个元素,则将其成本视为 0。
示例:令 N=5 且 K=1 且数组为 [3,5,4,2,1] 那么这里的答案是 6
解释:
The next jumping elements for:
1 is { }. Closest=none, so cost = 0
2 is { 1 }. Closest=1, so cost = 1
3 is { 1 , 2 }. Closest=2, so cost = 3
4 is { 1 , 2 , 3 }. Closest=2, so cost= 1
5 is { 1 , 2 , 3 , 4 }. Closest=3 or 4, so cost = 1
总成本是6
我知道一个可以在 O(N^2) 中运行的蛮力解决方案。但是 1 <= N <= 2 * 10^5 和 1 <= K,V[i] <= N。那么有什么更好的方法可以解决这个问题?
最佳答案
通过使用二叉树存储索引,您可以将其从 O(n^2) 减少到 O(n^lg(n))。
从空树 T 开始,从 1 -> N 迭代。在每一步中,当你在树中输入新索引时,你也可以得到最接近的索引。
关于algorithm - 跳转到下一个最近的元素,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/29856156/