P8664 [Lanqiao Cup 2018 NOI Qualifier A] Bill Payment Problem

It is common for several people to go out for a meal together. But when it is time to pay the bill, disputes often arise. Now there are $n$ people dining out, and their total spending is $S$ yuan. The $i$-th person brought $a_i$ yuan. Fortunately, the total amount of money everyone brought is enough to pay the bill, but the question is: how much should each person pay? To be fair, under the condition that the total amount paid is exactly $S$, we want the standard deviation of the amounts each person pays to be as small as possible. Here we agree that the amount each person pays can be any non-negative real number, i.e., it does not have to be an integer multiple of 1 cent. You need to output the minimum possible standard deviation. Introduction to standard deviation: standard deviation is the square root of the average of the squared differences between several numbers and their mean, and it is generally used to describe “how large the deviation is” among these numbers. Formally, let the amount paid by the $i$-th person be $b_i$ yuan, then the standard deviation is $s=\sqrt{\frac{1}{n}\sum_{i=1}^n(b_i-\frac{1}{n}\sum_{i=1}^n b_i)}$.

The first line contains two integers $n$ and $S$. The second line contains $n$ non-negative integers $a_1,\cdots,a_n$.

Output to standard output. Output the minimum standard deviation, rounded to $4$ decimal places. It is guaranteed that adding or subtracting $10^{-9}$ to the correct answer will not change the rounding result.

**Sample Explanation** 1. Everyone pays $2333/5$ yuan, and the standard deviation is 0. **Data Specification** For $10\%$ of the testdata, all $a_i$ are equal. For $30\%$ of the testdata, all non-zero $a_i$ are equal. For $60\%$ of the testdata, $n \le 1000$. For $80\%$ of the testdata, $n \le 10^5$. For all testdata, $n \le 5 \times 10^5$ and $0 \le a_i \le 10^9$. Translated by ChatGPT 5