#QUEUEWATER. 排队接水
排队接水
题目描述
n 个人排队在一个水龙头前接水,第 i 个人接水需要 t_i 秒。接水顺序由你安排:每个人接到水之前,需要等前面所有人接完。第 i 个人的等待时间等于从开始到他开始接水为止经过的时间(他自己接水的时间不计入他的等待时间)。请安排一个接水顺序,使得所有人的等待时间之和最小,输出这个最小值。
输入格式
第一行一个正整数 n,表示人数。 第二行 n 个正整数 t_1, t_2, …, t_n,第 i 个数表示第 i 个人接水需要的时间。
输出格式
一行一个整数,表示最小等待时间之和。
数据范围
1 ≤ n ≤ 2000,1 ≤ t_i ≤ 1000。答案可能超过 32 位整数范围,请使用 64 位整数。
样例
3
3 1 2
4
5
5 4 3 2 1
20
说明/提示
样例 1 解释:按 1 2 3 的顺序接水。第 1 人等待 0,第 2 人等待 1,第 3 人等待 1+2=3,总和 0+1+3=4。若按 3 1 2 的顺序,总和为 0+3+4=7,更大。
解析
思路:直观上,让接水快的人先接,后面的人等待的“被拖累时间”更少,总等待更小。
证明(交换论证):设相邻两人 A、B,A 在 B 前,接水时间 a、b。交换前,B 的等待受 A 影响,贡献 a;交换后 A 的等待贡献 b。两人其它等待不受影响,故交换前后总差为 (a-b)·(其余人数权重相同)。当 a > b 时交换可减少总等待,因此最优解中任意相邻两人满足前者 ≤ 后者,即按接水时间升序排列最优。
计算:设排序后第 i 位(从 0 开始)时间为 s_i,其等待时间为前缀和 Σ_{j<i} s_j,答案为 Σ_i (n-1-i)·s_i,用 64 位整数累加。
复杂度:排序 O(n log n),统计 O(n),空间 O(n)。
来源
人工命题 · 对比实验