CF1698B Rising Sand

有 $n$ 堆沙子，第 $i$ 堆有 $a_i$ 块沙子。如果 $1 < i < n$ 且 $a_i > a_{i-1} + a_{i+1}$，则称第 $i$ 堆“过高”。也就是说，如果某一堆沙子的数量比它左右两边的沙子数量之和还要多，则该堆为“过高”。（注意，数组两端的沙堆不能成为“过高”堆。） 现在给定一个整数 $k$。每次操作可以选择 $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$ 堆和第 $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]$。 此时第 $2$ 堆和第 $4$ 堆为“过高”堆，所以答案为 $2$。可以证明无法让超过 $2$ 堆同时成为“过高”堆。 在第二个测试样例中，任何一次操作都会使所有沙堆都加 $1$ 单位，因此“过高”堆的数量始终为 $0$。 在第三个测试样例中，可以对任意一堆加 $1$ 单位沙子。可以证明最多只能有 $1$ 堆成为“过高”堆。 由 ChatGPT 4.1 翻译