Qpwoeirut And The City

题意翻译

给定长为 $n$ 的数列 $\{h_n\}$，对于其中的一个元素 $h_i(1< i < n)$，我们称它为“好的”，当且仅当 $h_i>h_{i-1}$ 且 $h_i>h_{i+1}$。 你可以进行若干次操作，每次可以选定一个 $i(1\le i\le n)$，并将 $h_i$ 增加 $1$。求使得 $\{h_n\}$ 中 “好的”元素最多，至少需要多少次操作。 多测，$1\le t\le 10^4$，$3\le n\le 10^5$，$1\le h_i\le 10^9$，$\sum n\le 2\times10^5$。 Translated by @Sya_Resory

题目描述

Qpwoeirut has taken up architecture and ambitiously decided to remodel his city. Qpwoeirut's city can be described as a row of $ n $ buildings, the $ i $ -th ( $ 1 \le i \le n $ ) of which is $ h_i $ floors high. You can assume that the height of every floor in this problem is equal. Therefore, building $ i $ is taller than the building $ j $ if and only if the number of floors $ h_i $ in building $ i $ is larger than the number of floors $ h_j $ in building $ j $ . Building $ i $ is cool if it is taller than both building $ i-1 $ and building $ i+1 $ (and both of them exist). Note that neither the $ 1 $ -st nor the $ n $ -th building can be cool. To remodel the city, Qpwoeirut needs to maximize the number of cool buildings. To do this, Qpwoeirut can build additional floors on top of any of the buildings to make them taller. Note that he cannot remove already existing floors. Since building new floors is expensive, Qpwoeirut wants to minimize the number of floors he builds. Find the minimum number of floors Qpwoeirut needs to build in order to maximize the number of cool buildings.

输入输出格式

输入格式

The first line contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases. The first line of each test case contains the single integer $ n $ ( $ 3 \le n \le 10^5 $ ) — the number of buildings in Qpwoeirut's city. The second line of each test case contains $ n $ integers $ h_1, h_2, \ldots, h_n $ ( $ 1 \le h_i \le 10^9 $ ) — the number of floors in each of the buildings of the city. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

输出格式

For each test case, print a single integer — the minimum number of additional floors Qpwoeirut needs to build in order to maximize the number of cool buildings.

输入输出样例

输入样例 #1

6
3
2 1 2
5
1 2 1 4 3
6
3 1 4 5 5 2
8
4 2 1 3 5 3 6 1
6
1 10 1 1 10 1
8
1 10 11 1 10 11 10 1

输出样例 #1

2
0
3
3
0
4

说明

In the first test case, it is optimal for Qpwoeirut to make the second building cool by building $ 2 $ additional floors on top of it, making it taller than both of its adjacent buildings. The final heights of buildings will be $ [2, \underline{3}, 2] $ . In the second test case, the number of cool buildings is already maximized, so Qpwoeirut does not need to do anything. In the third test case, it is optimal for Qpwoeirut to make the third and fifth buildings cool by building $ 2 $ additional floors onto the third building and $ 1 $ additional floor onto the fifth building. The final heights of buildings will be $ [3, 1, \underline{6}, 5, \underline{6}, 2] $ . It can be shown that it is impossible to make more than $ 2 $ of the buildings cool, or to make $ 2 $ buildings cool using fewer than $ 3 $ additional floors. In the fourth test case, Qpwoeirut can either make the second building cool, or he can make the third building cool. Either way, he will be building $ 3 $ additional floors and maximizing the number of cool buildings. The final heights of buildings will be $ [4, 2, \underline{4}, 3, 5, 3, 6, 1] $ or $ [4, \underline{5}, 1, 3, 5, 3, 6, 1] $ . 

题目大意：
Qpwoeirut正在从事建筑行业，并雄心勃勃地决定重新规划他的城市。他的城市可以描述为一排$n$座建筑物，其中第$i$座建筑物高$h_i$层。如果一座建筑物比它左右两边的建筑物都高，则称其为“酷”建筑物。Qpwoeirut可以通过在任何建筑物上增加楼层来使城市中的“酷”建筑物数量最大化，同时要求增加的楼层数量最少。多组测试数据，$1\le t\le 10^4$，$3\le n\le 10^5$，$1\le h_i\le 10^9$，$\sum n\le 2\times10^5$。

输入输出数据格式：
输入格式：
- 第一行包含一个整数$t$（$1 \le t \le 10^4$）——测试用例的数量。
- 每个测试用例的第一行包含一个整数$n$（$3 \le n \le 10^5$）——Qpwoeirut城市的建筑物数量。
- 每个测试用例的第二行包含$n$个整数$h_1, h_2, \ldots, h_n$（$1 \le h_i \le 10^9$）——城市中每座建筑物的高度。

输出格式：
- 对于每个测试用例，打印一个整数——为了使“酷”建筑物的数量最大化，Qpwoeirut需要建造的最少额外楼层数量。

输入输出样例：
输入样例 #1：
```
6
3
2 1 2
5
1 2 1 4 3
6
3 1 4 5 5 2
8
4 2 1 3 5 3 6 1
6
1 10 1 1 10 1
8
1 10 11 1 10 11 10 1
```
输出样例 #1：
```
2
0
3
3
0
4
```题目大意： Qpwoeirut正在从事建筑行业，并雄心勃勃地决定重新规划他的城市。他的城市可以描述为一排$n$座建筑物，其中第$i$座建筑物高$h_i$层。如果一座建筑物比它左右两边的建筑物都高，则称其为“酷”建筑物。Qpwoeirut可以通过在任何建筑物上增加楼层来使城市中的“酷”建筑物数量最大化，同时要求增加的楼层数量最少。多组测试数据，$1\le t\le 10^4$，$3\le n\le 10^5$，$1\le h_i\le 10^9$，$\sum n\le 2\times10^5$。 输入输出数据格式： 输入格式： - 第一行包含一个整数$t$（$1 \le t \le 10^4$）——测试用例的数量。 - 每个测试用例的第一行包含一个整数$n$（$3 \le n \le 10^5$）——Qpwoeirut城市的建筑物数量。 - 每个测试用例的第二行包含$n$个整数$h_1, h_2, \ldots, h_n$（$1 \le h_i \le 10^9$）——城市中每座建筑物的高度。 输出格式： - 对于每个测试用例，打印一个整数——为了使“酷”建筑物的数量最大化，Qpwoeirut需要建造的最少额外楼层数量。 输入输出样例： 输入样例 #1： ``` 6 3 2 1 2 5 1 2 1 4 3 6 3 1 4 5 5 2 8 4 2 1 3 5 3 6 1 6 1 10 1 1 10 1 8 1 10 11 1 10 11 10 1 ``` 输出样例 #1： ``` 2 0 3 3 0 4 ```