← 返回题目列表

Codeforces · 1698/B

B. 沙子上涨

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

有 $$$n$$$ 堆沙子,其中第 $$$i$$$ 堆有 $$$a_i$$$ 沙块。如果 $$$1 < i < n$$$ 且 $$$a_i > a_{i-1} + a_{i+1}$$$,则第 $$$i$$$ 堆被称为太高。也就是说,如果一堆沙子的沙子数量多于相邻两个沙堆的沙子数量之和,则该沙堆就太高了。 (请注意,阵列两端的堆不能太高。)

给你一个整数 $$$k$$$。操作包括拾取 $$$k$$$ 连续的沙堆并向其中添加一个单位的沙子。形式上,选择 $$$1 \leq l,r \leq n$$$ 使得 $$$r-l+1=k$$$。然后对于所有$$$l \leq i \leq r$$$,更新$$$a_i \gets a_i+1$$$。

经过一些(可能为零)操作后,可以同时太高的桩的最大数量是多少?

输入

输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 1000$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$3 \leq n \leq 2 \cdot 10^5$$$; $$$1 \leq k \leq n$$$)——分别是沙堆的数量和操作的大小。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) - 桩的大小。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出一个整数 - 在一些(可能为零)操作后同时太高的堆的最大数量。

示例

输入 #1

3
5 2
2 9 2 4 1
4 4
1 3 2 1
3 1
1 3 1

输出 #1

2
0
1

注意

在第一个测试用例中,我们可以执行以下三个操作:

- 将一单位沙子添加到 $$$1$$$ 和 $$$2$$$ 堆中:$$$[\color{red}{3}, \color{red}{10}, 2, 4, 1]$$$。
- 将一单位沙子添加到 $$$4$$$ 和 $$$5$$$ 堆中:$$$[3, 10, 2, \color{red}{5}, \color{red}{2}]$$$。
- 将一单位沙子添加到堆 $$$3$$$ 和 $$$4$$$ 中:$$$[3, 10, \color{red}{3}, \color{red}{6}, 2]$$$。

在第二个测试用例中,任何操作都会将所有桩增加 $$$1$$$ 单位,因此太高的桩的数量将始终为 $$$0$$$。

在第三个测试用例中,我们可以将任意堆增加 $$$1$$$ 单位的沙子。可以证明太高桩的最大数量为$$$1$$$。