Problem E: 【2011基础】排队拍照
Memory Limit:64 MB
Time Limit:1.000 S
Judge Style:Text Compare
Creator:
Submit:218
Solved:71
Description
在一个美丽的景点,有N个同学想每人拍一张照片作为留念,于是他们就排好队一个一个来拍。但是呢,每个人拍照需要的时间是不同的,有些同学是在创作艺术,可能花费时间比较多,有些同学比较随意,只想证明自己到此一游而已。
考虑到排队排在后面的同学可能会等比较长的时间,为了让这个现象有所缓解,现在需要你来帮助他们找到一个排队的方案,使得所有人等待的时间总和最少。
Input
第一行包含一个整数N(N<=50000),表示有N个同学想拍照;
第二行包含N个用空格隔开的整数,表示每个人拍照所需的时间T1,T2,……,Tn(0<=Ti<=100000)。
第二行包含N个用空格隔开的整数,表示每个人拍照所需的时间T1,T2,……,Tn(0<=Ti<=100000)。
Output
仅有一行包含一个整数——所有人等待时间总和的最小值。
Sample Input Copy
5
2 3 1 5 4
Sample Output Copy
20
HINT
样例解释:
排队顺序(用每个人的编号表示)应该是 3,1,2,5,4,每个人拍照所需的时间分别是1,2,3,4,5, 这样的话每个人等待的时间分别是0,1,3, 6,10,所以总的等待时间就是0+1+3+6+10 = 20,不可能找到比这个等待时间更少的方案了。
数据范围:
15%的数据满足N<=30
30%的数据满足N<=100
50%的数据满足N<=1000
100%的数据满足N<=50000
排队顺序(用每个人的编号表示)应该是 3,1,2,5,4,每个人拍照所需的时间分别是1,2,3,4,5, 这样的话每个人等待的时间分别是0,1,3, 6,10,所以总的等待时间就是0+1+3+6+10 = 20,不可能找到比这个等待时间更少的方案了。
数据范围:
15%的数据满足N<=30
30%的数据满足N<=100
50%的数据满足N<=1000
100%的数据满足N<=50000