题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

Java 代码

import java.util.Scanner;

public class Main {

public static void main(String[] args) {

    Scanner scanner = new Scanner(System.in);

    final int N = scanner.nextInt();
    final double M = scanner.nextDouble();
    double[] H = new double[N];
    // Scanner scanner1 = new Scanner(System.in);

    for (int i = 0; i < H.length; i++) {

        H[i] = scanner.nextDouble();
    } // fuzhi


qs(H,0,N-1);//快排


    System.out.printf("%.4f", suan(H, N, M));//算法调用

}
public static void qs(double H[] ,int left,int right){

    int i,j;double temp,t;
    if(left>right) return;
    temp = H[left];
    i = left;
    j = right;
    while(i!=j){
        while(H[j]>=temp&&i<j)
        j--;

        while(H[i]<=temp&&i<j)
            i++;
        if(i<j){

            t=H[i];
            H[i] = H[j];
            H[j] = t;
        }

    }
    H[left] = H[i];
    H[i] = temp;

    qs(H, left, i-1);
    qs(H, i+1, right);
    return;

}

public static double suan(double[] H, int N, double M) {
    double cs = 0;
    double s = 0;
    double s1 = 0;
    double s2 = 0;

    s1 = (M   / N);
    cs = s1;
    // s1 = 666;
    // s1 = s1/N;

    for (int i = 0; i < N; i++) {
        if (H[i] <= cs) {
            s2 += ( s1-H[i] ) * (s1-H[i]);
            M = M - H[i];
            cs = (M) / (N - i - 1);

        } else {

            s2 += (cs - s1) * (cs - s1);
            M = M - cs;
            cs = (M) / (N - i-1 );

        }

    }

    s = Math.sqrt((s2 / N));
    return s;
}

}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla