algorithm - 乘坐出租车在两个城市之间旅行

Question

You want to get from town A to B being m miles apart using some number of cabs. Somewhere between the towns (or in one of them) there's a cab base (each cab starts its journey from the base). Each cab has fuel for some miles of travel (none of the cabs has to return to the base). Determine if your travel from A to B is possible.

INPUT:

Integers m,d,n (1<=d<=m<=10^8, 1<=n<=500,000) meaning (in that order): distance from A to B, distance from A to cab base, number of cabs. After that, n integers meaning that i-th cab has fuel for x_i-th miles of travel.

OUTPUT:

One integer: a minimum number of cabs you'll have to use to get from A to B or 0 if it's impossible.

我试着用我脑海中的第一个想法来解决它，但(毫不奇怪)这并不是一个好主意。也就是说，我所做的是:

sort(ALL(cabs));
reverse(ALL(cabs));

for(int i = 0; i < n; ++i)
{
    toPosition = position <= d ? d-position : position - d;

    if(cabs[0] <= toPosition) {printf("0"); return 0;}

    position += (cabs[0]-toPosition);
    cabs.erase(cabs.begin());
    ++solution;

    if(position >= m) {printf("%lld", solution); return 0;}
}

现在，toPosition 是从基地到我们所在的当前位置 的距离。然后，我们从基地乘坐油箱最满的出租车(如果没有这样的东西可以让我们更接近 B 镇，那么就没有解决方案)。我们相应地改变我们的位置(到给定出租车容量的最大值)，移除出租车，直到我们到达 B 镇。

我现在知道解决方案是错误的。我什至发现了一些失败的测试。但是，我不太明白为什么会这样。所以例如测试

14 4 2
10 8

它输出 0 而它应该输出 2。我知道这是因为它想要 10->8 而这里的正确顺序是 8 -> 10。现在问题出现了:

为什么顺序在这个问题中很重要？如果我们无论如何都必须走完从 A 到 B 的所有距离，直到我们到达基地位置或到达基地位置之后，我们必须让每辆出租车回溯，为什么不使用回溯任务最快的那些呢？

Answer 1

假设您有 3 辆出租车，其中只有 1 辆有足够的燃料到达 A，它可以让您距离基地 1 英里；一个有足够的燃料让你从基地到 B；最后一个有足够的燃料进行 2 英里的旅行。显然，您必须其次使用“最小”的出租车；如果你使用另一个，你就只能避开 B，出租车无法到达你，更不用说完成工作了。

所以，是的，顺序很重要。