TNT接力｜依赖思维

T3 - TNT接力

题目链接跳转：点击跳转

这道题是本次比赛的第三道题，但是许多参赛选手认为这道题是本场比赛最难的题目。

解题思路

1. 滑动窗口：使用滑动窗口技术，先在前 $K$ 个方块中计算有多少个空气方块。接着，随着窗口向右滑动，我们移除窗口左端的一个方块，并加入窗口右端的一个方块，更新空气方块的数量。

2. 最大空气方块数量：我们维护一个变量 mx，表示在当前窗口中最多有多少个空气方块。

3. 计算答案：每次计算答案时，使用 $K - \text{最大空气方块数量}$ 来表示最小的 TNT 方块数量，这表示需要多少步才能避免 TNT 的塌陷。如果 $K \geq N$，表示玩家可以直接跳过整个桥，输出 $-1$​。

时间复杂度

每次处理一个序列的时间复杂度是 $O(N)$，其中 $N$ 是方块序列的长度。整体复杂度为 $O(T \times N)$，其中 $T$ 是测试用例的数量。关于本体，还可以用二分来进一步优化。本文不过多陈述。

代码实现

本题的 C++ 代码如下：

#include <iostream>
#include <string>

using namespace std;

int solve(int N, int K, string S) {
    if (K >= N) return -1;
    ++K;
    int mx = 0, cur = 0;
    for (int i = 0; i < N; ++i) {
        if (S[i] == '-') ++cur;
        if (i - K >= 0 && S[i - K] == '-') --cur;
        mx = max(mx, cur);
    }
    return K - mx;
}

int main() {
    int T;
    cin >> T;
    for (int i = 0; i < T; i++) {
        int N, K;
        cin >> N >> K;
        string S;
        cin >> S;
        cout << solve(N, K, S) << '\n';
    }
    return 0;
}

本题的 Python 代码如下：

def solve(N: int, K: int, S: str) -> int:
    if K >= N:
        return -1
    mx, cur = 0, 0
    K += 1
    for i in range(N):
        if S[i] == '-':
            cur += 1
        if i - K >= 0 and S[i - K] == '-':
            cur -= 1
        mx = max(mx, cur)
    return K - mx


def main():
    T = int(input())
    for _ in range(T):
        temp = input().split()
        N, K = int(temp[0]), int(temp[1])
        S = input()
        print(solve(N, K, S))


if __name__ == '__main__':
    main()