用于此的线性时间解决方案

线性是指瓷砖数量的线性，对吧？

如果是这样，此解决方案（在 Java 中）仅迭代一次磁贴数组。

在每次迭代中，它还需要迭代 D 和 X 次，但就瓦片数组的大小而言，它将是线性的。

如果它听起来与您正在寻找的相似，请告诉我。

注意：为简化起见，我假设位置“0”的图块在第二个数字“0”处可用，因此有效地将第二个“0”视为您所站立的图块存在的时间，然后其他图块出现在第 1 秒、第 2 秒等。

    public class TestTiles {

        public static int calculateSecond(Integer x, Integer d, int[] tiles) {
            // start by making all positions unreachable (false)
            boolean[] posReachable = new boolean[x+1];
            // iterate each second only once
            for (int second = 0; second < tiles.length; second++) {
                int tile = tiles[second];  // this tile is available now
                // so mark all positions from "tile" to "tile + d" reachable
                for (int pos = tile; (pos <= tile + d) && pos <= x; pos++) {
                    posReachable[pos] = true;
                }
                // are all positions reachable now? if so, this is the second to return
                boolean reachable = true;
                for (int pos = 0; pos <= x; pos++) {
                    reachable &= posReachable[pos];
                }
                if (reachable) return second;
            }
            // we can't reach the position
            return -1;
        }

        public static void main(String[] args) {
            System.out.println(calculateSecond(7, 3, new int[]{0,1,3,1,4,2,5}));
            System.out.println(calculateSecond(20, 3, new int[]{0,1,3,1,4,2,5}));
            System.out.println(calculateSecond(2, 3, new int[]{0,1,3,1,4,2,5}));
            System.out.println(calculateSecond(4, 3, new int[]{0,1,3,1,4,2,5}));
            System.out.println(calculateSecond(15, 3, new int[]{0,12,3,9,6}));
        }

    }

以下建议应该需要时间 O（N * log（min（N， X/D）））。特别要注意的是，这是在 O（N * log（N）） 中，因此比你提出的算法或 mcdowella 提出的优先级队列算法具有更好的界限;在 O（N * （X + D）） 中，因此比 eugenioy 提出的算法具有更好的边界;不会随着 D 的增加而增加（如 mcdowella 的数组算法、eugenioy 的算法和 coproc 的算法）;此外，对于固定的 X 在 O（N） 中。

这个想法是保留一组我们仍然需要找到路径的间隔。我们将此集合存储在一个平衡树中，其键是区间的下界，其值是上限。当我们看到一个新图块时，我们将找到包含此图块的间隔（如果有），并在图块周围拆分间隔，丢弃任何小于 D 的结果间隔。当我们的地图是空的时，我们就完成了。

以下是 Haskell 中的完整实现。

import Data.Ix
import Data.Map
import qualified Data.Map as M

-- setup: the initial set of intervals is just the singleton from 0 to x
search :: Int -> Int -> [Int] -> Maybe Int
search d x = search_ d (insertCandidate d 0 x empty)

search_ :: Int -> Map Int Int -> [Int] -> Maybe Int
search_ d = go where
    -- first base case: we've found all the paths we care about
    go intervals _ | M.null intervals = Just 0
    -- second base case: we're out of tiles, and still don't have all the paths
    go _ [] = Nothing
    -- final case: we need to take a time step. add one, and recursively search the remaining time steps
    go intervals (tile:tiles) = (1+) <$> go newIntervals tiles where
        newIntervals = case lookupLE tile intervals of
            Just (lo, hi) | inRange (lo, hi) tile
                -> insertCandidate d lo tile
                .  insertCandidate d tile hi
                .  delete lo
                $  intervals
            _ -> intervals

-- only keep non-trivial intervals
insertCandidate :: Int -> Int -> Int -> Map Int Int -> Map Int Int
insertCandidate d lo hi m
    | hi - lo <= d = m
    | otherwise    = insert lo hi m

在 ghci 中运行它的几个例子（我无耻地从另一个答案中扯掉了这些例子）：

> search 3 7 [1,3,1,4,2,5]
Just 4
> search 3 20 [1,3,1,4,2,5]
Nothing
> search 3 2 [1,3,1,4,2,5]
Just 0
> search 3 4 [1,3,1,4,2,5]
Just 1
> search 3 15 [12,3,9,6]
Just 4

我会一个接一个地处理图块，因为它们在数组中，跟踪最大的可到达位置，并维护“待处理”图块的优先级队列。

1. 如果图块大于 X，请将其扔掉。
2. 如果瓷砖已经在可触及的区域内，请将其扔掉。
3. 如果目前无法访问该磁贴，请将其添加到挂起队列中。
4. 如果磁贴扩展了可访问区域，请执行此操作，并重新处理挂起队列中现在可访问的最近磁贴，或在此重新处理期间可访问的磁贴。
5. （如果现在可以访问 X，请停止）。

每个图块最多处理两次，每次处理的步长为 O（1），除了在小整数的优先级队列中添加和删除 min 的成本，为此有专门的算法 - 请参阅 https://cs.stackexchange.com/questions/2824/most-efficient-known-priority-queue-for-inserts。

[Python 中的这个解决方案类似于 mcdowella 的解决方案;但它没有使用优先级队列，而是简单地使用一个大小为 X 的数组来表示最多 X 的位置。它的复杂度是 ，所以它不是真正的线性，而是 N 中的线性 ...]O(N+min(N,X)*D)

该数组跟踪位置 1,...,X-1。通过跳转到最远的可到达图块，每个图块都会更新当前位置。world

def jumpAsFarAsPossible(currentPos, D, X, world):
  for jump in range(D,0,-1): # jump = D,D-1,...,1
    reachablePos = currentPos + jump
    if reachablePos >= X:
      return X
    if world[reachablePos]:
      return jumpAsFarAsPossible(reachablePos, D, X, world)
  return currentPos

def solve(X,D,A):
  currentPos = 0
  # initially there are no tiles
  world = X * [False]

  for k,tilePos in enumerate(A):
    if tilePos < X:
      world[tilePos] = True

    # how far can we move now?
    if currentPos+D >= tilePos:
      currentPos = jumpAsFarAsPossible(currentPos, D, X, world)

    # have we reached X?
    if currentPos == X:
      return k # success in k-th second

  return -1 # X could not be reached

这是另一种尝试：

创建一个大小为 X 的数组 B，将其初始化为 MAX_VALUE，然后填充元素 B[A[i]] = min（B[A[i]]， i），使 B 的每个元素要么很大，要么是该方块上第一次出现图块。

将当前时间初始化为零，然后从左到右沿着 B 工作，尝试从 0 跳到 X，跳转最多 D 的图块，使用不大于当前时间的 B 元素。如果您无法再往前走，请将当前时间增加到 B 中任何方块中的最小值，以便您进一步跳跃。

成本是 O（X log（D）） + O（N） - 你用成本 O（N） 的 A 来初始化 X，然后沿着 X 一步一步地工作。如果你在每个时间点保留一个优先级队列来覆盖 X 中的下一个 D 元素，你可以以不超过 log（D） 的成本找到 X 的最小可访问元素 - 同样，这些都是小整数，所以你可能会做得更好。

我的解决方案是.我有两个论点（好吧，一个借口和一个真实的论点）来为它辩护：O(N)+O(X/D)O(N)

借口是我应该有空间，我什至无法及时初始化它。因此，我假设数组是预先初始化的，并且由于我的部分只是将数组初始化为默认值，因此我很高兴地忽略它。（嘿，我说这是个借口）。O(X)O(N)O(X/D)

真正的论点是，不能真的大于 .我的意思是，如果我必须以每个位置最多为步长移动位置，则最小步数将是（这意味着平铺）。X/DNXDX/DX/D-1

• 因此，任何问题都是无法解决的。X/D-1 > N
• 因此，该算法很可能以 .if (X/D > N+1) return -1
• 所以，永远不会大于 。O(X/D)O(N)
• 所以，其实和.O(N)+O(X/D)O(N)

也就是说，我提出了我的解决方案：

数学设置

我将假设一个位置为 的“轨道”，因此它在左侧和右侧（我需要这个，因为我将谈论“最左边的瓷砖”和类似的东西）。轨道有位置，编号为 。最初，有一个图块，另一个图块位于 。0X0XX+10X0X

我把曲目分成几块。块大小是使任何两个相邻块加起来恰好的位置。第一个块是位置，第二个块是 ，第三个是 ，第四块是 ，依此类推，介于 和 之间。如果是偶数并且我们设置 ，则所有块的大小将相等。我觉得如果设置为并且块成对处理，实现可能会更容易一些，但我真的不知道（我还没有实现这个），并且算法对于任何算法基本上都是相同的，所以我会继续。DkD-kkD-kk1D-1Dk=D/2k1k

最后一个块可以被截断，但我只是假设它是它应该的大小，即使这意味着它超出了 .没关系。举个简单的例子，如果 ， ， ， 将有大小的块（即 、 、 、 、 ，位置不是轨道的一部分）。XX=30D=13k=656-7-6-7-60-56-1213-1819-2425-3131

从现在开始，我将对块使用数组表示法，即我将块编号称为 .kC[k]

非常重要的一点是，两个相邻的块加起来总是精确的位置，因为它保证了：D

• 如果每个块上至少有瓷砖，问题就解决了（即不再需要瓷砖）。
• 如果两个相邻的块上没有图块，则需要更多的图块。

如果有一个块在前面的任何一种情况下都没有落下（即一个没有图块，但前面和后面的块确实有图块），那么我们必须测量块中最左边的图块到右边，和块中最右边的图块之间的距离左边。如果此距离小于或等于 ，则此块不是问题。D

总而言之：根据以下规则，有些块是有问题的，有些则不是：

• 至少有一个图块的块永远不会有问题。
• 没有图块的块，以及也没有图块的邻居（左、右或两者）总是有问题的。
• 没有图块、有邻居和都有图块的块，当且仅当 .C[k]C[k-1]C[k+1]C[k+1].left - C[k-1].right > D

而且，跳入问题解决方案的部分：

• 当且仅当至少有一个有问题的块时，我们需要更多的图块来完成轨道。

因此，处理仓位的问题现在只处理块。这太棒了。O(X)O(N)

实施细节

在块数组中，每个块将具有以下属性：C[k]

• boolean ，初始化为 。problematictrue
• integer ，初始化为 。left-1
• integer ，初始化为 。right-1

此外，将有一个 ，初始化为数组中的元素数。这将滴答作响，当它达到零时，我们知道我们不需要更多的瓷砖。problematicCounterC

算法是这样的：

if (X/D > N+1) return -1;  // Taking care of rounding is left as an exercise

Let C = array of chunks as described above

For each C[k] // This is the O(X/D) part
{
  Let C[k].problematic = true
  Let C[k].left = -1
  Let C[k].right = -1
}

Let problematicCounter = number of elements in array C

Let C[k] be the chunk that contains position 0 (usually the first one, but I'll leave open the possibility of "sentinel" chunks)
Let C[k].problematic = false
Let C[k].left = 0
Let C[k].right = 0
Decrement problematicCounter

// The following steps would require tweaking if there is one single chunk on the track
// I do not consider that case as that would imply D >= 2*N, which is kind of ridiculous for this problem
Let C[k] be the chunk containing position X (the last position on the track)
Let C[k].problematic = false
Let C[k].left = X
Let C[k].right = X
Decrease problematicCounter

// Initialization done. Now for the loop.
// Everything inside the loop is O(1), so the loop itself is O(N)
For each A[i] in array A (the array specifying which tile to place in second i)
{
  Let C[k] be the chunk containing position A[i]

  If C[k].problematic == true
  {
    Let C[k].problematic = false;
    Decrement problematicCounter
  }

  If C[k].first == -1 OR C[k].first > A[i]
  {
    Let C[k].first = A[i]

    // Checks that C[k-1] and C[k-2] don't go off array index bounds left as an exercise
    If C[k-1].problematic == true AND C[k-2].last <> -1 AND C[k].first - C[k-2].last <= D
    {
      Let C[k-1].problematic = false
      Decrement problematicCounter
    }

  If C[k].last == -1 OR C[k].last < A[i]
  {
    Let C[k].last = A[i]

    // Checks that C[k+1] and C[k+2] don't go off array index bounds left as an exercise
    If C[k+1].problematic == true AND C[k+2].first <> -1 AND C[k+2].first - C[k].last <= D
    {
      Let C[k+1].problematic = false
      Decrement problematicCounter
    }

    If problematicCounter == 0 Then return k // and forget everything else
}

return -1