← 返回题目列表

Codeforces · 2126/B

B. 山上没有赌场

中文机器翻译题面 查看原题

给定一个由 $$$n$$$ 数字组成的数组 $$$a$$$ 和一个数字 $$$k$$$。值 $$$a_i$$$ 描述了第 $$$i$$$ 天的天气:如果第 $$$i$$$ 天下雨,则 $$$a_i = 1$$$;否则,如果第 $$$i$$$ 天天气良好,则 $$$a_i = 0$$$。

吉恩想要参观尽可能多的山峰。一次徒步到达山顶需要 $$$k$$$ 天,并且在这些天中的每一天,天气都必须良好 ($$$a_i = 0$$$)。也就是说,正式而言,只有当所有 $$$j$$$ $$$(i \leq j \leq i + k - 1)$$$ 的所有 $$$a_j = 0$$$ 时,他才能在 $$$i$$$ 那天开始徒步旅行。

每次徒步结束后,在开始下一次徒步之前,Jean 必须至少休息一天,这意味着在徒步旅行后的第二天,他不能再进行另一次徒步旅行。

求 Jean 可以访问的最大山峰数量。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 10^5$$$, $$$1 \le k \le n$$$)。

第二行包含 $$$n$$$ 数字 $$$a_i$$$ ($$$a_i \in \{0, 1\}$$$),其中 $$$a_i$$$ 表示第 $$$i$$$ 天的天气。

保证所有测试用例的 $$$n$$$ 总价值不超过 $$$10^5$$$。

输出

对于每个测试用例,输出一个整数:Jean 可以进行的最大徒步次数。

示例

输入
复制

5
5 1
0 1 0 0 0
7 3
0 0 0 0 0 0 0
3 1
1 1 1
4 2
0 1 0 1
6 2
0 0 1 0 0 0

输出
复制

3
2
0
0
2

注意

在第一个样本中:

  • Day $$$1$$$ — 天气很好,Jean 去徒步旅行。 ($$$a_1 = 0$$$)
  • Day $$$2$$$ — 强制休息。
  • Day $$$3$$$ — 天气又好,Jean 进行了第二次徒步旅行。 ($$$a_3 = 0$$$)
  • 天 $$$4$$$ — 休息。
  • Day $$$5$$$ — 天气很好,第三次徒步旅行。 ($$$a_5 = 0$$$)
因此,Jean 可以使 3 次加息,每一个都与强制休息日交替。

在第二个示例中:

  • 从 $$$1$$$ 到 $$$3$$$ — 三天的好天气,Jean 去徒步旅行。 ($$$a_1 = a_2 = a_3 = 0$$$)
  • Day $$$4$$$ — 强制休息。
  • 从 $$$5$$$ 到 $$$7$$$ — 又是三天好天气,Jean 进行了第二次徒步旅行。 ($$$a_5 = a_6 = a_7 = 0$$$)
总共,Jean 使 2 次加息.

在第三个示例中:

  • 没有好天气的日子($$$a_i = 1$$$ 对于所有 $$$i$$$)
Jean 无法进行任何徒步旅行。 答案:0