Monsters (easy version) (Codeforces 1785A)
Tags: Greedy, sortings

This is the easy version of the problem. In this version, you only need to find the answer once. In this version, hacks are not allowed.In a computer game, you are fighting against $$$n$$$ monsters. Monster number $$$i$$$ has $$$a_i$$$ health points, all $$$a_i$$$ are integers. A monster is alive while it has at least $$$1$$$ health point.You can cast spells of two types:  Deal $$$1$$$ damage to any single alive monster of your choice.  Deal $$$1$$$ damage to all alive monsters. If at least one monster dies (ends up with $$$0$$$ health points) as a result of this action, then repeat it (and keep repeating while at least one monster dies every time). Dealing $$$1$$$ damage to a monster reduces its health by $$$1$$$.Spells of type 1 can be cast any number of times, while a spell of type 2 can be cast at most once during the game.What is the smallest number of times you need to cast spells of type 1 to kill all monsters?

Input: Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.Each test case consists of two lines. The first line contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of monsters.The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — monsters' health points.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output: For each test case, print a single integer — the smallest number of times you need to cast spells of type 1 to kill all monsters.

Note: In the first test case, the initial health points of the monsters are $$$[3, 1, 2]$$$. It is enough to cast a spell of type 2:   Monsters' health points change to $$$[2, 0, 1]$$$. Since monster number $$$2$$$ dies, the spell is repeated.  Monsters' health points change to $$$[1, 0, 0]$$$. Since monster number $$$3$$$ dies, the spell is repeated.  Monsters' health points change to $$$[0, 0, 0]$$$. Since monster number $$$1$$$ dies, the spell is repeated.  Monsters' health points change to $$$[0, 0, 0]$$$. Since it is possible to use no spells of type 1 at all, the answer is $$$0$$$.In the second test case, the initial health points of the monsters are $$$[4, 1, 5, 4, 1, 1]$$$. Here is one of the optimal action sequences:   Using a spell of type 1, deal $$$1$$$ damage to monster number $$$1$$$. Monsters' health points change to $$$[3, 1, 5, 4, 1, 1]$$$.  Using a spell of type 1, deal $$$1$$$ damage to monster number $$$4$$$. Monsters' health points change to $$$[3, 1, 5, 3, 1, 1]$$$.  Using a spell of type 1, deal $$$1$$$ damage to monster number $$$4$$$ again. Monsters' health points change to $$$[3, 1, 5, 2, 1, 1]$$$.  Use a spell of type 2:  Monsters' health points change to $$$[2, 0, 4, 1, 0, 0]$$$. Since monsters number $$$2$$$, $$$5$$$, and $$$6$$$ die, the spell is repeated.  Monsters' health points change to $$$[1, 0, 3, 0, 0, 0]$$$. Since monster number $$$4$$$ dies, the spell is repeated.  Monsters' health points change to $$$[0, 0, 2, 0, 0, 0]$$$. Since monster number $$$1$$$ dies, the spell is repeated.  Monsters' health points change to $$$[0, 0, 1, 0, 0, 0]$$$.   Using a spell of type 1, deal $$$1$$$ damage to monster number $$$3$$$. Monsters' health points change to $$$[0, 0, 0, 0, 0, 0]$$$. Spells of type 1 are cast $$$4$$$ times in total. It can be shown that this is the smallest possible number.

Sample Inputs:
2
3
3 1 2
6
4 1 5 4 1 1

Sample Outputs:
0
4

Solution (Python):
cases = int(input())
for case in range(cases):
    n = int(input())
    health = sorted(list(map(int, input().split())))
    spell = 0
    count = 1
    for i in health:
        if i >= count:
            spell += i - count
            count += 1
    print(spell)

Solution (Python):
n = int(input())
for UU in range(n):
    nom = int(input())
    health = input().split()
    health = [int(i) for i in health]
    health.sort()
    turns = 0
    mmx = 0
    for i in range(0, len(health)):
        if health[i] - mmx > 0:
            mmx += 1
            turns += health[i] - mmx
    print(turns)

Solution (Python):
res = 0
n = int(input())
for i in range(n):
    m = int(input())
    nums = input().split()
    nums = [int(x) for x in nums]
    nums = sorted(nums)
    k = 1
    for j in range(m):
        if nums[j] >= k:
            res += nums[j] - k
            k += 1
    print(res)
    res = 0