TouchStone
  Please Login
Login Sign Up
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P2584
  • Problem
  • P2584【12月水题之王】合唱队
    Limits : Time Limit : 10000 MS   Memory Limit : 165536 KB
    Description

    有N个同学参加了何老板组织的欢乐合唱队。
    排练时,N个同学站成一排,但同学们高矮参差不齐,站在一起有碍观感。何老板认为,高度差比较大的两个同学站在一起是不大好看的,于是他想重新排一下队形,使得相邻两个同学的高度差的总和最小。

    Input Format

    第一行,一个整数N,表示有N个队员。
    第二行,N个空格间隔的整数,表示每个队员的身高。

    Output Format

    一行,一个整数,表示高度差之和的最小值。

    Sample Input

    4
    1 7 3 8

    Sample Output

    7

    Hint

    若采用1,7,3,8的站位方式,高度差之和为|1-7|+|7-3|+|3-8|=15
    若采用8,1,3,7的站位方式,高度差之和为|8-1|+|1-3|+|3-7|=12
    ......

    1<=N<=100000
    0<队员的身高<=10000