Rising Sand

题意翻译

给定一个序列 $a$，如果满足 $a_i > a_{i-1}+a_{i+1}$ 与 $1 < i < n$，那么就说这个数太高。 现在可以对序列进行若干个（可以为 $0$）形式如下的操作： 给一段长度为 $k$ 的区间每个数都加上 $1$。 求操作完之后太高的数的最大个数。 #### 数据范围与约定 $3 \le n \le 2 \times 10^5，k \le n，a_i \le 10^9, \sum n \le 10^5$

题目描述

There are $ n $ piles of sand where the $ i $ -th pile has $ a_i $ blocks of sand. The $ i $ -th pile is called too tall if $ 1 < i < n $ and $ a_i > a_{i-1} + a_{i+1} $ . That is, a pile is too tall if it has more sand than its two neighbours combined. (Note that piles on the ends of the array cannot be too tall.) You are given an integer $ k $ . An operation consists of picking $ k $ consecutive piles of sand and adding one unit of sand to them all. Formally, pick $ 1 \leq l,r \leq n $ such that $ r-l+1=k $ . Then for all $ l \leq i \leq r $ , update $ a_i \gets a_i+1 $ . What is the maximum number of piles that can simultaneously be too tall after some (possibly zero) operations?

输入输出格式

输入格式

The input consists of multiple test cases. The first line contains an integer $ t $ ( $ 1 \leq t \leq 1000 $ ) — the number of test cases. The description of the test cases follows. The first line of each test case contains two integers $ n $ and $ k $ ( $ 3 \leq n \leq 2 \cdot 10^5 $ ; $ 1 \leq k \leq n $ ) — the number of piles of sand and the size of the operation, respectively. The second line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le 10^9 $ ) — the sizes of the piles. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

输出格式

For each test case, output a single integer — the maximum number of piles that are simultaneously too tall after some (possibly zero) operations.

输入输出样例

输入样例 #1

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

输出样例 #1

2
0
1

说明

In the first test case, we can perform the following three operations: - Add one unit of sand to piles $ 1 $ and $ 2 $ : $ [\color{red}{3}, \color{red}{10}, 2, 4, 1] $ . - Add one unit of sand to piles $ 4 $ and $ 5 $ : $ [3, 10, 2, \color{red}{5}, \color{red}{2}] $ . - Add one unit of sand to piles $ 3 $ and $ 4 $ : $ [3, 10, \color{red}{3}, \color{red}{6}, 2] $ . Now piles $ 2 $ and $ 4 $ are too tall, so in this case the answer is $ 2 $ . It can be shown that it is impossible to make more than $ 2 $ piles too tall.In the second test case, any operation will increase all piles by $ 1 $ unit, so the number of too tall piles will always be $ 0 $ . In the third test case, we can increase any pile by $ 1 $ unit of sand. It can be shown that the maximum number of too tall piles is $ 1 $ .

**上升的沙堆**

**题意翻译**

给定一个序列 $a$，如果满足 $a_i > a_{i-1} + a_{i+1}$ 且 $1 < i < n$，那么称这个数太高。

现在可以对序列进行若干个（可以为 $0$）形式如下的操作：

选择一段长度为 $k$ 的区间，将该区间内的每个数都增加 $1$。

求操作完之后太高的数的最大个数。

#### 数据范围与约定
$3 \le n \le 2 \times 10^5，k \le n，a_i \le 10^9, \sum n \le 10^5$

**题目描述**

有 $ 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 $ 和 $ r $，然后对所有 $ l \leq i \leq r $，执行 $ a_i \gets a_i+1 $。

在进行了若干次（可能为零次）操作之后，同时太高的沙堆的最大数量是多少？

**输入输出格式**

**输入格式**

输入由多个测试用例组成。第一行包含一个整数 $ t $（$ 1 \leq t \leq 1000 $）——测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的第一行包含两个整数 $ n $ 和 $ k $（$ 3 \leq n \leq 2 \times 10^5 $；$ 1 \leq k \leq n $）——沙堆的数量和操作的大小。

每个测试用例的第二行包含 $ n $ 个整数 $ a_1, a_2, \ldots, a_n $（$ 1 \le a_i \le 10^9 $）——沙堆的大小。

保证所有测试用例的 $ n $ 之和不超过 $ 2 \times 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 $ 的沙子各增加一单位：$ [3, 10, 2, 4, 1] $。
- 将沙堆 $ 4 $ 和 $ 5 $ 的沙子各增加一单位：$ [3, 10, 2, 5, 2] $。
- 将沙堆 $ 3 $ 和 $ 4 $ 的沙子各增加一单位：$ [3, 10, 3, 6, 2] $。

现在沙堆 $ 2 $ 和 $ 4 $ 太高了，所以在这种情况下答案是 $ 2 $。可以证明不可能使超过 $ 2 $ 堆沙子同时太高。

在第二个测试用例中，任何操作都会使所有沙堆增加一单位沙子，所以太高的沙堆的数量将始终为 $ 0 $。

在第三个测试用例中，我们可以增加任意一堆沙子的一单位沙子。可以证明太高的沙堆的最大数量是 $ 1 $。**上升的沙堆** **题意翻译** 给定一个序列 $a$，如果满足 $a_i > a_{i-1} + a_{i+1}$ 且 $1 < i < n$，那么称这个数太高。 现在可以对序列进行若干个（可以为 $0$）形式如下的操作： 选择一段长度为 $k$ 的区间，将该区间内的每个数都增加 $1$。 求操作完之后太高的数的最大个数。 #### 数据范围与约定 $3 \le n \le 2 \times 10^5，k \le n，a_i \le 10^9, \sum n \le 10^5$ **题目描述** 有 $ 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 $ 和 $ r $，然后对所有 $ l \leq i \leq r $，执行 $ a_i \gets a_i+1 $。 在进行了若干次（可能为零次）操作之后，同时太高的沙堆的最大数量是多少？ **输入输出格式** **输入格式** 输入由多个测试用例组成。第一行包含一个整数 $ t $（$ 1 \leq t \leq 1000 $）——测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含两个整数 $ n $ 和 $ k $（$ 3 \leq n \leq 2 \times 10^5 $；$ 1 \leq k \leq n $）——沙堆的数量和操作的大小。 每个测试用例的第二行包含 $ n $ 个整数 $ a_1, a_2, \ldots, a_n $（$ 1 \le a_i \le 10^9 $）——沙堆的大小。 保证所有测试用例的 $ n $ 之和不超过 $ 2 \times 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 $ 的沙子各增加一单位：$ [3, 10, 2, 4, 1] $。 - 将沙堆 $ 4 $ 和 $ 5 $ 的沙子各增加一单位：$ [3, 10, 2, 5, 2] $。 - 将沙堆 $ 3 $ 和 $ 4 $ 的沙子各增加一单位：$ [3, 10, 3, 6, 2] $。 现在沙堆 $ 2 $ 和 $ 4 $ 太高了，所以在这种情况下答案是 $ 2 $。可以证明不可能使超过 $ 2 $ 堆沙子同时太高。 在第二个测试用例中，任何操作都会使所有沙堆增加一单位沙子，所以太高的沙堆的数量将始终为 $ 0 $。 在第三个测试用例中，我们可以增加任意一堆沙子的一单位沙子。可以证明太高的沙堆的最大数量是 $ 1 $。