问题:
我刚刚解决了问题。我想知道我是否正确解决了问题。
算法:
我从起点开始，尝试添加剩下的汽油以远距离行驶。如果value
int PPT(int P[], int D[], int N)
{
int start = 0, end = 1, cur_ptr = P[0] - D[0], i = start;
while(start != end)
{
if(cur_ptr < 0)
{
start = (i + 1) % N;
end = (start + 1) % N;
cur_ptr = 0;
if(start == 0) return -1; // if start again becomes 0 then no solution exists
}
i = (i + 1) % N;
cur_ptr += P[i] - D[i];
}
}
最佳答案
start != end始终成立。因此，如果有解决方案，您的算法将产生无限循环。此外，我不明白为什么end应该是start + 1。
这是另一种方法:
考虑以下功能:
此函数将在到达泵i之前计算剩余的汽油。该功能可以如下所示:
该函数从petrol = 0开始。您会看到此配置无效，因为在泵4处，剩余汽油为负数。此外，还有一个解决方案，因为最后一个泵(再次是启动泵)的剩余汽油为正。
如果我们选择其他起点会怎样？函数的基本形状保持不变。它只是移到左侧。此外，由于函数以petrol = 0开头，因此函数减少了C(start)。最终剩余的燃料在这种情况下不起作用，因为这会增加当前的汽油。
任务是找到一个允许所有start为正的C(i)。最小C(i)很明显就是这种情况，对于start = 4就是这种情况。
函数C(i)的计算可以迭代完成，因此可以线性进行。您从0到N进行了一次迭代。可以在此迭代过程中以恒定的时间找到最小值(通过与当前最小值进行比较)。因此，总体时间复杂度为O(n)。
关于c++ - 汽油泵巡回演出，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/18457751/