在给定 Y 通配符的情况下，确定 X 卡中最长可能的连续运行

Question

我目前正在解决一个问题，该问题表明我有 X 张卡，其中 X-Y 卡是带有整数的卡，而 Y 卡是可以采用任何整数值的通配符。

我正在尝试实现Python代码，该代码可以识别X卡中最长可能的连续运行。 （长度为 l 的游程是 l 张卡的序列，对于某个整数 a，其具有整数 (a,a+1,a+2,…,a+l−1)。）

def longest_run(X, Y, cards):
    cards.sort()

    longest_run_length = 1
    current_run_length = 1

    for i in range(1, X - Y):
        if cards[i] == cards[i - 1] + 1:
            current_run_length += 1
        elif cards[i] != cards[i - 1]:
            gap = cards[i] - cards[i - 1] - 1
            if Y >= gap:
                current_run_length += gap
                Y -= gap

        longest_run_length = max(longest_run_length, current_run_length)
   
    longest_run_length += Y

    
    return longest_run_length

# Sample Input
input_data = "11 2\n2 5 4 3 3 8 7 11 15"
X, Y = map(int, input_data.split("\n")[0].split())
cards = list(map(int, input_data.split("\n")[1].split()))

result = longest_run(X, Y, cards)
print(result)

我尝试实现这段代码，但存在各种问题。首先，在识别间隙并用通配符填充它们之后，我的代码没有继续搜索可以添加到运行中的其他数字。其次，由于我想找到可能的最长游程长度，因此从最小的卡整数值开始可能会导致不正确的解决方案并用完所有通配符，而另一方面，如果我从另一个整数值开始，我可能会得到更长的长度运行。

非常感谢有关此事的任何帮助，并感谢您的阅读。

Answer 1

您已经正确识别了代码的局限性。它只查看从输入中最小值开始的序列，但解决方案可能必须从其他地方开始。也要考虑这些，您可以通过从中减去左侧（一个序列和一个间隙）来减少当前窗口，这样您就可以恢复一些通配符以重新使用以将更多内容扩展到右侧，并将其视为一种竞争替代方案到之前找到的解决方案。这就是滑动窗口技术。 我首先将输入转换为交替大小：

[size of sequence, size of gap], [size of sequence, size of gap], ...

建议代码：

def longest_run(x, y, cards):
    if not cards:
        return y
    cards = sorted(set(cards))  # eliminate duplicates
    # turn into consecutive sequence-size and gap-size pairs
    sizes = [[1]]
    for prev, curr in zip(cards, cards[1:]):
        if curr > prev + 1:
            sizes[-1].append(curr - prev - 1)  # gap size
            sizes.append([1])                  # size of new sequence
        else:
            sizes[-1][0] += 1                  # update size of sequence
    # add closing
    sizes[-1].append(y)                        # gap size (infinity)
    
    # sliding window technique:
    wildcards = y   # currently available wildcards
    score = best = 0
    ahead = iter(sizes)  # iterator that runs ahead of loop iterator
    for seq_first, gap_first in sizes:
        # grow window to the right
        while wildcards:
            last = next(ahead, None)
            if not last:
                return best
            seq_last, gap_last = last
            score += seq_last + min(wildcards, gap_last)
            wildcards = max(0, wildcards - gap_last)
            best = max(score, best)
        # shrink window from the left
        wildcards = gap_first
        score -= seq_first + gap_first
    
    return best

NB：没有使用

x

，因为在我看来它是

cards

的长度，即如果可能的话，可以使用所有卡片。