309548: CF1697A. Parkway Walk
Memory Limit：256 MB
Time Limit：1 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Parkway Walk
题意翻译
## 题目描述 你正穿过你家附近的一条林荫大道，道路上有 $n+1$ 个长椅，从左到右依次编号为 $1$ 到 $n+1$。编号为 $i$ 和 $i+1$ 的长椅之间的距离是 $a_i$ 米。 最初，你有 $m$ 个单位的能量。要走 $1$ 米的距离，你要花费 $1$ 单位的能量。如果你没有能量，你就不能行走。另外，你可以通过坐在长椅上恢复能量（这也是恢复能量的唯一方法）。当你坐着的时候，只要你想，你可以恢复任意整数的能量（坐的时间越长，你恢复的能量就越多）。请注意，你的能量可以超过 $m$。 你的任务是找到你必须恢复的最小能量（通过坐在长椅上），以便从长椅 $1$ 走到长椅 $n+1$（并结束你的行走）。 你必须回答 $t$ 组独立的测试数据。 ## 输入格式 输入的第一行包含一个整数 $t (1 \le t \le 100)$测试数据的组数。接着是t组测试数据。 测试数据的第一行包含两个整数 $n$ 和 $ m(1≤n≤100;1≤m≤104)$。 测试数据的第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n(1≤a_i≤100)$，其中 $a_i$ 是编号为 $i$ 和 $i+1$ 的长椅之间的距离。 ## 输出格式 对于每个测试案例，输出一个整数——表示在相应的测试数据中，你必须恢复的最小能量（通过坐在长椅上），以便你从长椅 $1$ 到达长椅 $n+1$（并结束行走）。 ## 样例 #1 ### 样例输入 #1 ``` 3 3 1 1 2 1 4 5 3 3 5 2 5 16 1 2 3 4 5 ``` ### 样例输出 #1 ``` 3 8 0 ``` ## 提示 在样例的第 $1$ 组测试数据中，你可以花费 $1$ 单位能量走到长椅 $2$，然后在长椅 $2$ 上坐下并恢复 $2$ 单位能量，再花费 $2$ 单位能量走到长椅 $3$，然后再恢复 $1$ 单位能量并走到长椅 $4$。 在样例的第 $3$ 组测试数据中，你有足够的能量直接走到长椅 $6$，根本不用坐下休息恢复能量。题目描述
You are walking through a parkway near your house. The parkway has $ n+1 $ benches in a row numbered from $ 1 $ to $ n+1 $ from left to right. The distance between the bench $ i $ and $ i+1 $ is $ a_i $ meters. Initially, you have $ m $ units of energy. To walk $ 1 $ meter of distance, you spend $ 1 $ unit of your energy. You can't walk if you have no energy. Also, you can restore your energy by sitting on benches (and this is the only way to restore the energy). When you are sitting, you can restore any integer amount of energy you want (if you sit longer, you restore more energy). Note that the amount of your energy can exceed $ m $ . Your task is to find the minimum amount of energy you have to restore (by sitting on benches) to reach the bench $ n+1 $ from the bench $ 1 $ (and end your walk). You have to answer $ t $ independent test cases.输入输出格式
输入格式
The first line of the input contains one integer $ t $ ( $ 1 \le t \le 100 $ ) — the number of test cases. Then $ t $ test cases follow. The first line of the test case contains two integers $ n $ and $ m $ ( $ 1 \le n \le 100 $ ; $ 1 \le m \le 10^4 $ ). The second line of the test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le 100 $ ), where $ a_i $ is the distance between benches $ i $ and $ i+1 $ .
输出格式
For each test case, print one integer — the minimum amount of energy you have to restore (by sitting on benches) to reach the bench $ n+1 $ from the bench $ 1 $ (and end your walk) in the corresponding test case.
输入输出样例
输入样例 #1
3
3 1
1 2 1
4 5
3 3 5 2
5 16
1 2 3 4 5输出样例 #1
3
8
0说明
In the first test case of the example, you can walk to the bench $ 2 $ , spending $ 1 $ unit of energy, then restore $ 2 $ units of energy on the second bench, walk to the bench $ 3 $ , spending $ 2 $ units of energy, restore $ 1 $ unit of energy and go to the bench $ 4 $ . In the third test case of the example, you have enough energy to just go to the bench $ 6 $ without sitting at all.Input
题意翻译
## 题目描述 你正穿过你家附近的一条林荫大道，道路上有 $n+1$ 个长椅，从左到右依次编号为 $1$ 到 $n+1$。编号为 $i$ 和 $i+1$ 的长椅之间的距离是 $a_i$ 米。 最初，你有 $m$ 个单位的能量。要走 $1$ 米的距离，你要花费 $1$ 单位的能量。如果你没有能量，你就不能行走。另外，你可以通过坐在长椅上恢复能量（这也是恢复能量的唯一方法）。当你坐着的时候，只要你想，你可以恢复任意整数的能量（坐的时间越长，你恢复的能量就越多）。请注意，你的能量可以超过 $m$。 你的任务是找到你必须恢复的最小能量（通过坐在长椅上），以便从长椅 $1$ 走到长椅 $n+1$（并结束你的行走）。 你必须回答 $t$ 组独立的测试数据。 ## 输入格式 输入的第一行包含一个整数 $t (1 \le t \le 100)$测试数据的组数。接着是t组测试数据。 测试数据的第一行包含两个整数 $n$ 和 $ m(1≤n≤100;1≤m≤104)$。 测试数据的第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n(1≤a_i≤100)$，其中 $a_i$ 是编号为 $i$ 和 $i+1$ 的长椅之间的距离。 ## 输出格式 对于每个测试案例，输出一个整数——表示在相应的测试数据中，你必须恢复的最小能量（通过坐在长椅上），以便你从长椅 $1$ 到达长椅 $n+1$（并结束行走）。 ## 样例 #1 ### 样例输入 #1 ``` 3 3 1 1 2 1 4 5 3 3 5 2 5 16 1 2 3 4 5 ``` ### 样例输出 #1 ``` 3 8 0 ``` ## 提示 在样例的第 $1$ 组测试数据中，你可以花费 $1$ 单位能量走到长椅 $2$，然后在长椅 $2$ 上坐下并恢复 $2$ 单位能量，再花费 $2$ 单位能量走到长椅 $3$，然后再恢复 $1$ 单位能量并走到长椅 $4$。 在样例的第 $3$ 组测试数据中，你有足够的能量直接走到长椅 $6$，根本不用坐下休息恢复能量。Output
**题目大意**：
你正在穿过一条林荫大道，这条大道上有 $n+1$ 个长椅，从左到右依次编号为 $1$ 到 $n+1$。相邻两个长椅之间的距离分别是 $a_1, a_2, \ldots, a_n$ 米。最初，你有 $m$ 个单位的能量，每走1米需要花费1单位能量。你可以通过坐在长椅上恢复能量（这是恢复能量的唯一方法），每次可以恢复任意整数的能量，且能量可以超过初始的 $m$ 单位。你的任务是找到至少需要恢复多少能量，才能从长椅 $1$ 走到长椅 $n+1$。
**输入数据格式**：
- 输入的第一行包含一个整数 $t$，表示测试数据的组数。
- 每组测试数据有两行，第一行包含两个整数 $n$ 和 $m$，第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$。
**输出数据格式**：
- 对于每组测试数据，输出一个整数，表示至少需要恢复的能量单位数。
**样例输入输出**：
输入：
```
3
3 1
1 2 1
4 5
3 3 5 2
5 16
1 2 3 4 5
```
输出：
```
3
8
0
```
**说明**：
- 在第一组样例中，你可以先花费1单位能量走到长椅2，然后恢复2单位能量，再花费2单位能量走到长椅3，接着恢复1单位能量并走到长椅4。
- 在第三组样例中，你有足够的能量直接走到长椅6，不需要坐下恢复能量。**题目大意**： 你正在穿过一条林荫大道，这条大道上有 $n+1$ 个长椅，从左到右依次编号为 $1$ 到 $n+1$。相邻两个长椅之间的距离分别是 $a_1, a_2, \ldots, a_n$ 米。最初，你有 $m$ 个单位的能量，每走1米需要花费1单位能量。你可以通过坐在长椅上恢复能量（这是恢复能量的唯一方法），每次可以恢复任意整数的能量，且能量可以超过初始的 $m$ 单位。你的任务是找到至少需要恢复多少能量，才能从长椅 $1$ 走到长椅 $n+1$。 **输入数据格式**： - 输入的第一行包含一个整数 $t$，表示测试数据的组数。 - 每组测试数据有两行，第一行包含两个整数 $n$ 和 $m$，第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$。 **输出数据格式**： - 对于每组测试数据，输出一个整数，表示至少需要恢复的能量单位数。 **样例输入输出**： 输入： ``` 3 3 1 1 2 1 4 5 3 3 5 2 5 16 1 2 3 4 5 ``` 输出： ``` 3 8 0 ``` **说明**： - 在第一组样例中，你可以先花费1单位能量走到长椅2，然后恢复2单位能量，再花费2单位能量走到长椅3，接着恢复1单位能量并走到长椅4。 - 在第三组样例中，你有足够的能量直接走到长椅6，不需要坐下恢复能量。
你正在穿过一条林荫大道，这条大道上有 $n+1$ 个长椅，从左到右依次编号为 $1$ 到 $n+1$。相邻两个长椅之间的距离分别是 $a_1, a_2, \ldots, a_n$ 米。最初，你有 $m$ 个单位的能量，每走1米需要花费1单位能量。你可以通过坐在长椅上恢复能量（这是恢复能量的唯一方法），每次可以恢复任意整数的能量，且能量可以超过初始的 $m$ 单位。你的任务是找到至少需要恢复多少能量，才能从长椅 $1$ 走到长椅 $n+1$。
**输入数据格式**：
- 输入的第一行包含一个整数 $t$，表示测试数据的组数。
- 每组测试数据有两行，第一行包含两个整数 $n$ 和 $m$，第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$。
**输出数据格式**：
- 对于每组测试数据，输出一个整数，表示至少需要恢复的能量单位数。
**样例输入输出**：
输入：
```
3
3 1
1 2 1
4 5
3 3 5 2
5 16
1 2 3 4 5
```
输出：
```
3
8
0
```
**说明**：
- 在第一组样例中，你可以先花费1单位能量走到长椅2，然后恢复2单位能量，再花费2单位能量走到长椅3，接着恢复1单位能量并走到长椅4。
- 在第三组样例中，你有足够的能量直接走到长椅6，不需要坐下恢复能量。**题目大意**： 你正在穿过一条林荫大道，这条大道上有 $n+1$ 个长椅，从左到右依次编号为 $1$ 到 $n+1$。相邻两个长椅之间的距离分别是 $a_1, a_2, \ldots, a_n$ 米。最初，你有 $m$ 个单位的能量，每走1米需要花费1单位能量。你可以通过坐在长椅上恢复能量（这是恢复能量的唯一方法），每次可以恢复任意整数的能量，且能量可以超过初始的 $m$ 单位。你的任务是找到至少需要恢复多少能量，才能从长椅 $1$ 走到长椅 $n+1$。 **输入数据格式**： - 输入的第一行包含一个整数 $t$，表示测试数据的组数。 - 每组测试数据有两行，第一行包含两个整数 $n$ 和 $m$，第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$。 **输出数据格式**： - 对于每组测试数据，输出一个整数，表示至少需要恢复的能量单位数。 **样例输入输出**： 输入： ``` 3 3 1 1 2 1 4 5 3 3 5 2 5 16 1 2 3 4 5 ``` 输出： ``` 3 8 0 ``` **说明**： - 在第一组样例中，你可以先花费1单位能量走到长椅2，然后恢复2单位能量，再花费2单位能量走到长椅3，接着恢复1单位能量并走到长椅4。 - 在第三组样例中，你有足够的能量直接走到长椅6，不需要坐下恢复能量。