题目描述

贪心算法，根据题意知道每个人付的钱越接近平均值标准差越小，如果有人的钱达不到平均值，就全部付掉，剩下的钱由剩下的人平分

Java 代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");

        int n = Integer.parseInt(str[0]);
        int s = Integer.parseInt(str[1]);

        int[] a = new int[n];

        str = br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(str[i]);
        }

        br.close();

        Arrays.sort(a);//排序减少循环的次数

        double res = 0;
        double avg = (double) s / n;

        for (int i = 0; i < n; i++) {

            if (a[i] >= s / ( n - i )) {//如果剩下的每个人的钱大于当前平均值，那么剩下的s将由这些人平分
                res += (n - i) * Math.pow((double) s / (n - i) - avg, 2);
                break;
            }

            res += Math.pow(a[i] - avg, 2);//人的钱少于平均值的时候
            s -= a[i];
        }

        System.out.printf("%.4f\n", Math.sqrt(res / n));

    }
}