Traps (Codeforces 1684D)
Tags: Greedy, sortings

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.

Input: 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$$$.

Output: 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.

Note: 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:  Do not jump over any trap.Total damage: $$$5 + 10 + 11 + 5 = 31$$$. Jump over the $$$1$$$-st trap.Total damage: $$$\underline{0} + (10 + 1) + (11 + 1) + (5 + 1) = 29$$$. Jump over the $$$2$$$-nd trap.Total damage: $$$5 + \underline{0} + (11 + 1) + (5 + 1) = 23$$$. Jump over the $$$3$$$-rd trap.Total damage: $$$5 + 10 + \underline{0} + (5 + 1) = 21$$$. 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$$$.

Sample Inputs:
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

Sample Outputs:
0
21
9
6
0

Solution (Python):
I = input
R = lambda : map(int, I().split())
for i in range(int(I())):
    (n, k) = R()
    a = sorted([v + i for (i, v) in enumerate(R())])
    print(sum(a[:-k]) - (n - k) * (0 + n - k - 1) // 2)

Solution (Python):
I = input
R = lambda : map(int, I().split())
for i in range(int(I())):
    (n, k) = R()
    a = sorted([v + i for (i, v) in enumerate(R())])
    print(sum(a[:-k]) - (n - k) * (0 + n - k - 1) // 2)

Solution (Python):
f = int(input())
for i in range(f):
    (n, k) = map(int, input().split())
    g = list(map(int, input().split()))
    h = [x + y for (x, y) in enumerate(g)]
    print(sum(sorted(h)[:n - k]) - (n - k) * (n - k - 1) // 2)