codechef walk解决方案背后的解释
Explanation behind codechef walk solution
在解决 codechef 问题 WALK 时，我想出了一种使用分而治之的方法来解决问题的算法，根据我的算法，我们找到数组中的最大值并将数组分成两部分（一个从开始到 Max 元素和另一半从 Max 元素的下一个到数组的末尾）然后我们找到数组的第一部分（竞争 Max elemeny 的部分）的初始速度：Max +（n- 1) 其中 n 是数组那部分中的元素数....我们对数组的每个部分都执行此操作，在计算每个部分的初始速度后，我们检查数组的某个部分的初始速度是否为小于或等于 Max + 1，其中 Max 是数组部分的最大元素，就在所考虑的部分之前，如果是这种情况，我们什么都不做，我们找出 Max + 1 与初始速度之间的差异和将该差异添加到之前的部分的初始速度正在考虑的部分，我们不断重复这个过程，直到不需要更多的改变。
现在这个算法肯定会工作，但它会超过时间限制。当我看到社论时，它有这个问题的一行解决方案。有人可以向我解释那个解决方案吗？我无法理解。
提前致谢。
设初速度为V。
当他们在第一个（基于 0 的索引）商店时，他们的速度仍然是 V，而且 V >= W1。
当他们穿过它并前往第二家商店时，速度变为 V-1。我们知道 V-1 >= W2。
同样，当他们穿过它并前往第三家商店时，速度变为 V-2。我们知道 V-2 >= W3。
继续这种方式，我们看到这个关系成立：
V-i >= [0,n-1] 中所有 i 的 Wi
V0 >= W0 + 0
V1 >= W1 + 1
V2 >= W2 + 2
V3 >= W3 + 3 ...
因此，对于所有 i，Vi >= Wi + i。
选择所有Wi+i中最大的V
在解决 codechef 问题 WALK 时，我想出了一种使用分而治之的方法来解决问题的算法，根据我的算法，我们找到数组中的最大值并将数组分成两部分（一个从开始到 Max 元素和另一半从 Max 元素的下一个到数组的末尾）然后我们找到数组的第一部分（竞争 Max elemeny 的部分）的初始速度：Max +（n- 1) 其中 n 是数组那部分中的元素数....我们对数组的每个部分都执行此操作，在计算每个部分的初始速度后，我们检查数组的某个部分的初始速度是否为小于或等于 Max + 1，其中 Max 是数组部分的最大元素，就在所考虑的部分之前，如果是这种情况，我们什么都不做，我们找出 Max + 1 与初始速度之间的差异和将该差异添加到之前的部分的初始速度正在考虑的部分，我们不断重复这个过程，直到不需要更多的改变。 现在这个算法肯定会工作，但它会超过时间限制。当我看到社论时，它有这个问题的一行解决方案。有人可以向我解释那个解决方案吗？我无法理解。 提前致谢。
设初速度为V。 当他们在第一个（基于 0 的索引）商店时，他们的速度仍然是 V，而且 V >= W1。 当他们穿过它并前往第二家商店时，速度变为 V-1。我们知道 V-1 >= W2。 同样，当他们穿过它并前往第三家商店时，速度变为 V-2。我们知道 V-2 >= W3。 继续这种方式，我们看到这个关系成立： V-i >= [0,n-1] 中所有 i 的 Wi
V0 >= W0 + 0
V1 >= W1 + 1
V2 >= W2 + 2
V3 >= W3 + 3 ...
因此，对于所有 i，Vi >= Wi + i。
选择所有Wi+i中最大的V