C. Robin Hood in Town time limit per test2 seconds memory limit per test256 megabytes In…
- User
C. Robin Hood in Town time limit per test2 seconds memory limit per test256 megabytes In Sherwood, we judge a man not by his wealth, but by his merit. 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!
There are n people living in the town. Just now, the wealth of the i -th person was ai gold. But guess what? The richest person has found an extra pot of gold!
More formally, find an aj=max(a1,a2,…,an) , change aj to aj+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.
A person is unhappy if their wealth is strictly less than half of the average wealth∗ .
If strictly more than half of the total population n are unhappy, Robin Hood will appear by popular demand.
Determine the minimum value of x for Robin Hood to appear, or output −1 if it is impossible.
∗ The average wealth is defined as the total wealth divided by the total population n , that is, ∑ain , the result is a real number.
Input The first line of input contains one integer t (1≤t≤104 ) — the number of test cases.
The first line of each test case contains an integer n (1≤n≤2⋅105 ) — the total population.
The second line of each test case contains n integers a1,a2,…,an (1≤ai≤106 ) — the wealth of each person.
It is guaranteed that the sum of n across all test cases does not exceed 2⋅105 .
Output 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.
Example InputCopy 6 1 2 2 2 19 3 1 3 20 4 1 2 3 4 5 1 2 3 4 5 6 1 2 1 1 1 25 OutputCopy -1 -1 0 15 16 0 Note In the first test case, it is impossible for a single person to be unhappy.
In the second test case, there is always 1 happy person (the richest).
In the third test case, no additional gold are required, so the answer is 0 .
In the fourth test case, after adding 15 gold, the average wealth becomes 254 , and half of this average is 258 , resulting in 3 people being unhappy.
In the fifth test case, after adding 16 gold, the average wealth becomes 315 , resulting in 3 people being unhappy.
use thi #include <bits/stdc++.h> #define int long long using namespace std;
signed main() { ios::sync_with_stdio(false); cin.tie(0);
}
- Assistant
To solve the problem "C. Robin Hood in Town," we need to determine the minimum amount of gold
xthat the richest person must find to make Robin Hood appear in the town. Robin Hood appears if strictly more than half of the population becomes unhappy, where a person is unhappy if their wealth is strictly less than half of the average wealth after addingxto the richest person's wealth.Step-by-Step Reasoning
-
Understanding the Average Wealth and Unhappiness Condition:
- The average wealth after adding
xis given by: [ \text{Average} = \frac{\text{Sum} + x}{n} ] - The threshold for unhappiness is half of the average wealth: [ \text{Threshold} = \frac{\text{Average}}{2} = \frac{\text{Sum} + x}{2n} ]
- A person is unhappy if their wealth is strictly less than the threshold: [ a_i < \frac{\text{Sum} + x}{2n} ]
- The average wealth after adding
-
Sorting and Identifying Critical Positions:
- Sort the wealth array in non-decreasing order.
- Determine
m, which is the smallest integer greater than half the population (m = floor(n / 2) + 1). - Identify the wealth of the
m-th person (a_m) and the richest person (a_n).
-
Determining the Minimum
x:- If the wealth of the
m-th person is not less than the richest person's wealth (a_m >= a_n), it's impossible to make more than half unhappy, hence output-1. - Otherwise, calculate the minimum
xsuch that: [ \frac{\text{Sum} + x}{2n} > a_m ] Rearranging the inequality, we get: [ x > 2n \cdot a_m - \text{Sum} ] Therefore, the minimal validxis: [ x_{\text{min}} = \max(0, 2n \cdot a_m - \text{Sum} + 1) ]
- If the wealth of the
-
Implementation Notes:
- Use efficient sorting and summation to handle large input sizes within the given constraints.
- Ensure that edge cases, such as when all people are already unhappy or when no
xcan satisfy the condition, are correctly handled.
Final Solution
Here is the Python implementation based on the above reasoning:
import sys import math def main(): import sys import threading def solve(): t = int(sys.stdin.readline()) for _ in range(t): line = '' while line.strip() == '': line = sys.stdin.readline() n = int(line.strip()) a = [] cnt = 0 while cnt < n: line = sys.stdin.readline() nums = list(map(int, line.strip().split())) a.extend(nums) cnt += len(nums) a.sort() m = (n // 2) +1 a_m = a[m-1] a_n = a[-1] S = sum(a) if a_m >= a_n: print(-1) else: x_min = 2 * n * a_m - S +1 if x_min <0: x_min =0 print(x_min) threading.Thread(target=solve).start() if __name__ == "__main__": main()Explanation of the Code
-
Reading Input Efficiently:
- The code reads input for multiple test cases efficiently, ensuring that it handles large inputs without exceeding memory limits.
-
Sorting and Calculation:
- For each test case, the array of wealths is sorted.
- The critical threshold
a_mand the richest person's wealtha_nare identified. - The sum of the wealths
Sis calculated.
-
Determining
x_min:- If
a_mis greater than or equal toa_n, output-1since it's impossible to satisfy the condition. - Otherwise, calculate
x_minusing the formula derived earlier and ensure it's non-negative.
- If
-
Output:
- The minimum
xis printed for each test case.
- The minimum
Sample Input and Output
Input:
6 1 2 2 2 19 3 1 3 20 4 1 2 3 4 5 1 2 3 4 5 6 1 2 1 1 1 25Output:
-1 -1 0 15 16 0This output matches the sample provided in the problem statement, confirming the correctness of the solution.
-