问题 4298 --3. 排队接水

4298: 3. 排队接水

题目描述

  “五一”劳动节到了,向阳小学五年级安排了一个小组的同学到文化广场搞清洁。广场边上只有一个水龙头,要求每一个同学带一个桶接水搞清洁,由于每个同学所带的桶大小不同,接满水所用的时间也不同,现在已知每一个同学的桶接满水所需要的时间,要求所有同学都要排队等候接水,注意接满水后的同学马上去搞清洁,不再等候,对于一个排好队的顺序,可以计算出所有同学等候接水的时间的总和。如有4个同学,他们接满水所需的时间分别是5、3、6、7,则第一个同学接水时,第二、三、四个同学都要等5个单位的时间,第二个同学接水时,则第三、四个同学都要等3个单位时间,第三个同学接水时,则第四个同学要等6个单位的时间,所有同学等候的时间共为:5*3+3*2+6*1=27。但如果同学们排队顺序改一下,他们接满水所需的时间分别是7、5、6、3,则所有同学等候的时间共为:7*3+5*2+6*1=37。现在给出每一个同学接满水所需的时间,请你安排一种排队顺序,使得所有同学等候的时间总和为最小,输出这个最小值。

输入

从文件water.in中读入数据,第一行为一个正整数N(1<N<=100),表示共有N个同学,接下来N行,每行一个正整数Y(1<y<200),依次表示同学接满水所需要的时间。

输出

结果输出到文件water.out中,只有一个数,表示所有同学等候的时间总和的最小值。

样例输入输出

输入#1 复制
4
5
3
6
7
输出#1 复制
25

提示

序号 标题 作者 发表时间 费用 订购数 操作