Traps

题意翻译

这里有 $ n $ 个陷阱，你需要按照给出的顺序穿过这些陷阱，每个陷阱将会对你造成 $ a_i $ 的伤害 你有至多 $k$ 次机会跳过这些陷阱，可以避免你所跳过的陷阱给你造成的伤害，不过接下来的所有陷阱都会给你多造成 $ 1 $ 点伤害 跳过陷阱所造成的额外伤害会叠加，如果你当前已经跳过了 $ 3 $ 个陷阱，接下来的陷阱给你造成的伤害将会是 $ a_i +3 $ 现在需要你求出受到的最小伤害

题目描述

There are $ n $ traps numbered from $ 1 $ to $ n $ . You will go through them one by one in order. The $ i $ -th trap deals $ a_i $ base damage to you. Instead of going through a trap, you can jump it over. You can jump over no more than $ k $ traps. If you jump over a trap, it does not deal any damage to you. But there is an additional rule: if you jump over a trap, all next traps damages increase by $ 1 $ (this is a bonus damage). Note that if you jump over a trap, you don't get any damage (neither base damage nor bonus damage). Also, the bonus damage stacks so, for example, if you go through a trap $ i $ with base damage $ a_i $ , and you have already jumped over $ 3 $ traps, you get $ (a_i + 3) $ damage. You have to find the minimal damage that it is possible to get if you are allowed to jump over no more than $ k $ traps.

输入输出格式

输入格式

The input consists of multiple test cases. The first line contains a single integer $ t $ ( $ 1 \le t \le 100 $ ) — the number of test cases. Description of the test cases follows. The first line of each test case contains two integers $ n $ and $ k $ ( $ 1 \le n \le 2 \cdot 10^5 $ , $ 1 \le k \le n $ ) — the number of traps and the number of jump overs that you are allowed to make. The second line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le 10^9 $ ) — base damage values of all traps. 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 minimal total damage that it is possible to get if you are allowed to jump over no more than $ k $ traps.

输入输出样例

输入样例 #1

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

输出样例 #1

0
21
9
6
0

说明

In the first test case it is allowed to jump over all traps and take $ 0 $ damage. In the second test case there are $ 5 $ ways to jump over some traps: 1. Do not jump over any trap.Total damage: $ 5 + 10 + 11 + 5 = 31 $ . 2. Jump over the $ 1 $ -st trap.Total damage: $ \underline{0} + (10 + 1) + (11 + 1) + (5 + 1) = 29 $ . 3. Jump over the $ 2 $ -nd trap.Total damage: $ 5 + \underline{0} + (11 + 1) + (5 + 1) = 23 $ . 4. Jump over the $ 3 $ -rd trap.Total damage: $ 5 + 10 + \underline{0} + (5 + 1) = 21 $ . 5. Jump over the $ 4 $ -th trap.Total damage: $ 5 + 10 + 11 + \underline{0} = 26 $ . To get minimal damage it is needed to jump over the $ 3 $ -rd trap, so the answer is $ 21 $ . In the third test case it is optimal to jump over the traps $ 1 $ , $ 3 $ , $ 4 $ , $ 5 $ , $ 7 $ : Total damage: $ 0 + (2 + 1) + 0 + 0 + 0 + (2 + 4) + 0 = 9 $ .

**题目大意：**

这个题目描述了一个有多个陷阱的场景，你需要按顺序穿过这些陷阱，每个陷阱都会对你造成一定的伤害。你有一定次数的跳跃机会，可以跳过陷阱从而避免伤害，但之后的所有陷阱都会造成额外的一点伤害。跳过陷阱的额外伤害会累积。目标是求出在不超过跳跃次数限制下，可能受到的最小总伤害。

**输入数据格式：**

- 输入包含多个测试用例。
- 第一行包含一个整数 $ t $（$ 1 \le t \le 100 $），表示测试用例的数量。
- 每个测试用例的第一行包含两个整数 $ n $ 和 $ k $（$ 1 \le n \le 2 \cdot 10^5 $，$ 1 \le k \le n $），分别表示陷阱的数量和允许的最大跳跃次数。
- 每个测试用例的第二行包含 $ n $ 个整数 $ a_1, a_2, \ldots, a_n $（$ 1 \le a_i \le 10^9 $），表示每个陷阱的基础伤害值。
- 保证所有测试用例的 $ n $ 之和不超过 $ 2 \cdot 10^5 $。

**输出数据格式：**

- 对于每个测试用例，输出一个整数，表示在不超过 $ k $ 次跳跃的情况下可能受到的最小总伤害。

**输入输出样例：**

**输入样例 #1:**
```
5
4 4
8 7 1 4
4 1
5 10 11 5
7 5
8 2 5 15 11 2 8
6 3
1 2 3 4 5 6
1 1
7
```

**输出样例 #1:**
```
0
21
9
6
0
```

**说明：**

- 在第一个测试用例中，可以跳过所有陷阱而不受伤害。
- 在第二个测试用例中，有五种跳跃陷阱的方式，计算每种方式的总伤害，找出最小值为21。
- 在第三个测试用例中，最优策略是跳过陷阱1、3、4、5、7，总伤害为9。**题目大意：** 这个题目描述了一个有多个陷阱的场景，你需要按顺序穿过这些陷阱，每个陷阱都会对你造成一定的伤害。你有一定次数的跳跃机会，可以跳过陷阱从而避免伤害，但之后的所有陷阱都会造成额外的一点伤害。跳过陷阱的额外伤害会累积。目标是求出在不超过跳跃次数限制下，可能受到的最小总伤害。 **输入数据格式：** - 输入包含多个测试用例。 - 第一行包含一个整数 $ t $（$ 1 \le t \le 100 $），表示测试用例的数量。 - 每个测试用例的第一行包含两个整数 $ n $ 和 $ k $（$ 1 \le n \le 2 \cdot 10^5 $，$ 1 \le k \le n $），分别表示陷阱的数量和允许的最大跳跃次数。 - 每个测试用例的第二行包含 $ n $ 个整数 $ a_1, a_2, \ldots, a_n $（$ 1 \le a_i \le 10^9 $），表示每个陷阱的基础伤害值。 - 保证所有测试用例的 $ n $ 之和不超过 $ 2 \cdot 10^5 $。 **输出数据格式：** - 对于每个测试用例，输出一个整数，表示在不超过 $ k $ 次跳跃的情况下可能受到的最小总伤害。 **输入输出样例：** **输入样例 #1:** ``` 5 4 4 8 7 1 4 4 1 5 10 11 5 7 5 8 2 5 15 11 2 8 6 3 1 2 3 4 5 6 1 1 7 ``` **输出样例 #1:** ``` 0 21 9 6 0 ``` **说明：** - 在第一个测试用例中，可以跳过所有陷阱而不受伤害。 - 在第二个测试用例中，有五种跳跃陷阱的方式，计算每种方式的总伤害，找出最小值为21。 - 在第三个测试用例中，最优策略是跳过陷阱1、3、4、5、7，总伤害为9。