Mark the Dust Sweeper

题意翻译

题目描述：给定一个长度为 $n$ 自然数列 $a$ ，每次操作可选取正整数 $i,j$ ，其中 $i,j$ 满足 $i<j $ 且 $a_i,a_{i+1},...,a_{j-1},a_j$均大于 $0$ ，使 $a_i-1,a_j+1$。 问最少多少次操作能使 $a_1,a_2,...,a_{n-1}$ 均等于 $0$。 输入格式： 第一行一个整数 $t$ 代表数据组数。 对于每组数据，第一行为一个整数 $n$ ；第二行 $n$ 个整数，第 $i$ 个数代表 $a_i$。 输出格式： 对于每组数据输出一行一个整数，为最小的操作数。 $1 \le t\le 10^4,2 \le n\le 2\times 10^5,0 \le a_i \le 10^9$ 题目保证所有数据的 $n$ 之和不超过 $2\times 10^5$。

题目描述

Mark is cleaning a row of $ n $ rooms. The $ i $ -th room has a nonnegative dust level $ a_i $ . He has a magical cleaning machine that can do the following three-step operation. - Select two indices $ i<j $ such that the dust levels $ a_i $ , $ a_{i+1} $ , $ \dots $ , $ a_{j-1} $ are all strictly greater than $ 0 $ . - Set $ a_i $ to $ a_i-1 $ . - Set $ a_j $ to $ a_j+1 $ . Mark's goal is to make $ a_1 = a_2 = \ldots = a_{n-1} = 0 $ so that he can nicely sweep the $ n $ -th room. Determine the minimum number of operations needed to reach his goal.

输入输出格式

输入格式

The first line contains a single integer $ t $ ( $ 1\leq t\leq 10^4 $ ) — the number of test cases. The first line of each test case contains a single integer $ n $ ( $ 2\leq n\leq 2\cdot 10^5 $ ) — the number of rooms. The second line of each test case contains $ n $ integers $ a_1 $ , $ a_2 $ , ..., $ a_n $ ( $ 0\leq a_i\leq 10^9 $ ) — the dust level of each room. It is guaranteed that the sum of $ n $ across all test cases does not exceed $ 2\cdot 10^5 $ .

输出格式

For each test case, print a line containing a single integer — the minimum number of operations. It can be proven that there is a sequence of operations that meets the goal.

输入输出样例

输入样例 #1

4
3
2 0 0
5
0 2 0 2 0
6
2 0 3 0 4 6
4
0 0 0 10

输出样例 #1

3
5
11
0

说明

In the first case, one possible sequence of operations is as follows. - Choose $ i=1 $ and $ j=2 $ , yielding the array $ [1,1,0] $ . - Choose $ i=1 $ and $ j=3 $ , yielding the array $ [0,1,1] $ . - Choose $ i=2 $ and $ j=3 $ , yielding the array $ [0,0,2] $ . At this point, $ a_1=a_2=0 $ , completing the process.In the second case, one possible sequence of operations is as follows. - Choose $ i=4 $ and $ j=5 $ , yielding the array $ [0,2,0,1,1] $ . - Choose $ i=2 $ and $ j=3 $ , yielding the array $ [0,1,1,1,1] $ . - Choose $ i=2 $ and $ j=5 $ , yielding the array $ [0,0,1,1,2] $ . - Choose $ i=3 $ and $ j=5 $ , yielding the array $ [0,0,0,1,3] $ . - Choose $ i=4 $ and $ j=5 $ , yielding the array $ [0,0,0,0,4] $ . In the last case, the array already satisfies the condition.

**题目大意：**

给定一个长度为 $ n $ 的自然数列 $ a $，每次操作可以选取正整数 $ i,j $，其中 $ i,j $ 满足 $ i < j $ 且 $ a_i, a_{i+1}, ..., a_{j-1}, a_j $ 均大于 $ 0 $，使得 $ a_i - 1, a_j + 1 $。问最少需要多少次操作能使 $ a_1, a_2, ..., a_{n-1} $ 均等于 $ 0 $。

**输入输出数据格式：**

**输入格式：**

- 第一行一个整数 $ t $ 代表数据组数。
- 对于每组数据，第一行为一个整数 $ n $；第二行 $ n $ 个整数，第 $ i $ 个数代表 $ a_i $。

**输出格式：**

- 对于每组数据输出一行一个整数，为最小的操作数。

**数据范围：**

- $ 1 \le t \le 10^4 $
- $ 2 \le n \le 2 \times 10^5 $
- $ 0 \le a_i \le 10^9 $

**题目保证所有数据的 $ n $ 之和不超过 $ 2 \times 10^5 $。****题目大意：** 给定一个长度为 $ n $ 的自然数列 $ a $，每次操作可以选取正整数 $ i,j $，其中 $ i,j $ 满足 $ i < j $ 且 $ a_i, a_{i+1}, ..., a_{j-1}, a_j $ 均大于 $ 0 $，使得 $ a_i - 1, a_j + 1 $。问最少需要多少次操作能使 $ a_1, a_2, ..., a_{n-1} $ 均等于 $ 0 $。 **输入输出数据格式：** **输入格式：** - 第一行一个整数 $ t $ 代表数据组数。 - 对于每组数据，第一行为一个整数 $ n $；第二行 $ n $ 个整数，第 $ i $ 个数代表 $ a_i $。 **输出格式：** - 对于每组数据输出一行一个整数，为最小的操作数。 **数据范围：** - $ 1 \le t \le 10^4 $ - $ 2 \le n \le 2 \times 10^5 $ - $ 0 \le a_i \le 10^9 $ **题目保证所有数据的 $ n $ 之和不超过 $ 2 \times 10^5 $。**