题意翻译

有一个长度为 $n$ 的数组 $a$，其中 $a_i \in \{0,1\}$，$0$ 表示晴天，$1$ 表示雨天。
一次登山需要连续 $k$ 个晴天（即连续 $k$ 个 $0$）。每次登山结束后，必须至少休息一天（即不能连续两天开始新的登山）。
求最多能进行多少次登山。

关键观察

• 只有连续的一段晴天（称为一个“晴天块”）才可能进行登山。
• 在一个长度为 $L$ 的晴天块中，每次登山占用 $k$ 个晴天，并且两次登山之间必须至少间隔 $1$ 天（可以是晴天或雨天，但因为是同一个块内，所以只能是晴天）。因此，除了最后一次登山外，每次登山后面都要跟一个休息日。
• 因此，进行 $x$ 次登山需要的总天数至少为：$$x \cdot k + (x-1) \cdot 1 = x(k+1) - 1$$ 这个值必须 $\le L$，即$$x \le \frac{L+1}{k+1}$$
• 由于 $x$ 是整数，一个块内最多能进行的登山次数为$$\left\lfloor \frac{L+1}{k+1} \right\rfloor$$

算法步骤

1. 读入 $t$ 组测试数据。
2. 对每组数据：
   • 读入 $n, k$ 和数组 $a$。
   • 扫描数组，找出所有连续的 $0$ 的长度。
   • 对每个长度 $len$，累加 $\left\lfloor \dfrac{len+1}{k+1} \right\rfloor$ 到答案。
   • 输出答案。

复杂度分析

• 只需一次 $O(n)$ 扫描，空间 $O(1)$。
• 所有测试用例的总 $n$ 不超过 $10^5$，因此总复杂度 $O(\sum n)$。

代码实现（C++）

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    
    int ans = 0;
    int len = 0;
    for (int i = 0; i < n; ++i) {
        if (a[i] == 0) {
            len++;
        } else {
            if (len > 0) {
                ans += (len + 1) / (k + 1);
                len = 0;
            }
        }
    }
    if (len > 0) ans += (len + 1) / (k + 1);
    
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

正确性说明

• 每个晴天块独立，因为雨天天然提供了休息日，且不同块之间的间隔至少为 $1$（雨天），所以不会互相影响。
• 在一个块内，最优策略就是尽可能紧凑地安排登山：每次登山后紧跟一个休息日（除了最后一次），这样能最大化次数。公式 $\left\lfloor \dfrac{L+1}{k+1} \right\rfloor$ 正是这种紧凑安排下可得到的最大次数。
• 反证法：若存在一种安排得到 $x$ 次登山，则必然满足 $x(k+1)-1 \le L$，所以 $x \le \frac{L+1}{k+1}$，因此 $x$ 不会超过公式值。而构造法：将块视为 $L+1$ 个位置（末尾虚拟一个休息日），然后每 $k+1$ 个位置分配一次登山（前 $k$ 个为登山，第 $k+1$ 个为休息），即可达到公式值。因此公式是最优的。

示例验证

• 样例1：$[0,1,0,0,0], k=1$
  块长度：$1$ → $(1+1)/2=1$；$3$ → $(3+1)/2=2$；总和 $3$，输出 $3$。
• 样例2：全 $0$，$n=7,k=3$
  块长度 $7$ → $(7+1)/4=2$，输出 $2$。
• 样例3：全 $1$，无块 → $0$。
• 样例4：$[0,1,0,1], k=2$
  两个块长度均为 $1$ → $(1+1)/3=0$，总和 $0$。
• 样例5：$[0,0,1,0,0,0], k=2$
  块长度 $2$ → $(2+1)/3=1$；块长度 $3$ → $(3+1)/3=1$；总和 $2$，输出 $2$。

全部匹配示例输出。