TouchStone
  Please Login
Login Sign Up
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P3904
  • Problem
  • P3904列队拍照
    Limits : Time Limit : - MS   Memory Limit : 65536 KB
    Judgment Tips : 1000
    Description

    NK信竞班的n名同学排成一排,准备拍合影。但是,有些同学的身高差很大,这让何老板觉得排出的照片不美观。他想从新排列一下这n名同学,使得相邻两人的身高差的平均值尽可能小。请你帮他计算出这个最小均值。

    Input Format

    第一行,一个整数n(2<=n<=100000)
    第二行,n个空格间隔的整数,表示每个同学的身高(1<=身高<=10000)。

    Output Format

    一行,一个实数,表示所求最小均值。保留两个小数位。

    Sample Input 1

    3
    4 2 4

    Sample Output 1

    1.00

    Sample Input 2

    13
    8 22 49 90 91 57 12 89 45 57 28 18 60 

    Sample Output 2

    6.92

    Hint

    样例说明,总共有两种排队方式:

    一: 2 4 4    身高差均值为(|4-2|+|4-4|)/2 = 1.00
    二: 4 2 4    升高差均值为(|2-4|+|4-2|)/2 = 2.00

    最小解为1.00