Income Inequality
면접 대비시간 제한2초메모리 제한1024 MB
가구 소득이 주어질 때 상위 x%가 보유한 부의 비율에서 x를 뺀 값의 최댓값을 구한다.
문제
According to Wikipedia, in 2021, the top 1% of households own 32.3% of the wealth in the United States. More generally, for any given percentage x, we could look at the data and state that the top x% of households own y% of the wealth.
It's obvious that for all societies with some inequality, it is always the case that y > x, except for x = 0 and x = 100. Of all possible choices for x, what is the maximum value of y – x?
Given the incomes of all people in a society, determine the maximum value of y – x where the top x% of the people have y% of the society's wealth.
입력
The first input line contains a single integer, n (2 ≤ n ≤ 106), indicating the number of people in the society.
The second input line contains n integers; each integer, m (1 ≤ m ≤ 1012), provides the wealth of a household in the society. Please note that the income values are not necessarily distinct.
출력
Print the maximum possible value of y – x, where the top x% of households in the society own y% of the society's wealth. Any answer within an absolute or relative error of 10-6 will be accepted.