codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1784A.md (3585B)


      1 Source: https://codeforces.com/problemset/problem/1784/A
      2 
      3 A. Monsters (easy version)
      4 
      5 time limit per test
      6 
      7 4 seconds
      8 
      9 memory limit per test
     10 
     11 512 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 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.
     22 
     23 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.
     24 
     25 You can cast spells of two types:
     26 
     27 1. Deal $1$ damage to any single alive monster of your choice.
     28 2. 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).
     29 
     30 Dealing $1$ damage to a monster reduces its health by $1$.
     31 
     32 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.
     33 
     34 What is the smallest number of times you need to cast spells of type 1 to kill all monsters?
     35 
     36 Input
     37 
     38 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.
     39 
     40 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.
     41 
     42 The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$) — monsters' health points.
     43 
     44 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
     45 
     46 Output
     47 
     48 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.
     49 
     50 Example
     51 
     52 Input
     53 
     54 ```
     55 2
     56 
     57 3
     58 
     59 3 1 2
     60 
     61 6
     62 
     63 4 1 5 4 1 1
     64 ```
     65 
     66 Output
     67 
     68 ```
     69 0
     70 4
     71 ```
     72 
     73 Note
     74 
     75 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:
     76 
     77 * Monsters' health points change to $[2, 0, 1]$. Since monster number $2$ dies, the spell is repeated.
     78 * Monsters' health points change to $[1, 0, 0]$. Since monster number $3$ dies, the spell is repeated.
     79 * Monsters' health points change to $[0, 0, 0]$. Since monster number $1$ dies, the spell is repeated.
     80 * Monsters' health points change to $[0, 0, 0]$.
     81 
     82 Since it is possible to use no spells of type 1 at all, the answer is $0$.
     83 
     84 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:
     85 
     86 * Using a spell of type 1, deal $1$ damage to monster number $1$. Monsters' health points change to $[3, 1, 5, 4, 1, 1]$.
     87 * Using a spell of type 1, deal $1$ damage to monster number $4$. Monsters' health points change to $[3, 1, 5, 3, 1, 1]$.
     88 * 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]$.
     89 * Use a spell of type 2:
     90   + Monsters' health points change to $[2, 0, 4, 1, 0, 0]$. Since monsters number $2$, $5$, and $6$ die, the spell is repeated.
     91   + Monsters' health points change to $[1, 0, 3, 0, 0, 0]$. Since monster number $4$ dies, the spell is repeated.
     92   + Monsters' health points change to $[0, 0, 2, 0, 0, 0]$. Since monster number $1$ dies, the spell is repeated.
     93   + Monsters' health points change to $[0, 0, 1, 0, 0, 0]$.
     94 * Using a spell of type 1, deal $1$ damage to monster number $3$. Monsters' health points change to $[0, 0, 0, 0, 0, 0]$.
     95 
     96 Spells of type 1 are cast $4$ times in total. It can be shown that this is the smallest possible number.