2014C.md (2565B)
1 Source: https://codeforces.com/problemset/problem/2014/C 2 3 C. Robin Hood in Town 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 In Sherwood, we judge a man not by his wealth, but by his merit. 22 23 Look around, the rich are getting richer, and the poor are getting poorer. We need to take from the rich and give to the poor. We need Robin Hood! 24 25 There are $n$ people living in the town. Just now, the wealth of the $i$-th person was $a_i$ gold. But guess what? The richest person has found an extra pot of gold! 26 27 More formally, find an $a_j=max(a_1, a_2, \dots, a_n)$, change $a_j$ to $a_j+x$, where $x$ is a non-negative integer number of gold found in the pot. If there are multiple maxima, it can be any one of them. 28 29 A person is unhappy if their wealth is strictly less than half of the average wealth$^{\text{∗}}$. 30 31 If strictly more than half of the total population $n$ are unhappy, Robin Hood will appear by popular demand. 32 33 Determine the minimum value of $x$ for Robin Hood to appear, or output $-1$ if it is impossible. 34 35 $^{\text{∗}}$The average wealth is defined as the total wealth divided by the total population $n$, that is, $\frac{\sum a_i}{n}$, the result is a real number. 36 37 Input 38 39 The first line of input contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases. 40 41 The first line of each test case contains an integer $n$ ($1 \le n \le 2\cdot10^5$) — the total population. 42 43 The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^6$) — the wealth of each person. 44 45 It is guaranteed that the sum of $n$ across all test cases does not exceed $2 \cdot 10^5$. 46 47 Output 48 49 For each test case, output one integer — the minimum number of gold that the richest person must find for Robin Hood to appear. If it is impossible, output $-1$ instead. 50 51 Example 52 53 Input 54 55 ``` 56 6 57 58 1 59 60 2 61 62 2 63 64 2 19 65 66 3 67 68 1 3 20 69 70 4 71 72 1 2 3 4 73 74 5 75 76 1 2 3 4 5 77 78 6 79 80 1 2 1 1 1 25 81 ``` 82 83 Output 84 85 ``` 86 -1 87 -1 88 0 89 15 90 16 91 0 92 ``` 93 94 Note 95 96 In the first test case, it is impossible for a single person to be unhappy. 97 98 In the second test case, there is always $1$ happy person (the richest). 99 100 In the third test case, no additional gold are required, so the answer is $0$. 101 102 In the fourth test case, after adding $15$ gold, the average wealth becomes $\frac{25}{4}$, and half of this average is $\frac{25}{8}$, resulting in $3$ people being unhappy. 103 104 In the fifth test case, after adding $16$ gold, the average wealth becomes $\frac{31}{5}$, resulting in $3$ people being unhappy.