(一处)排队打水 Python 贪心
题目描述
有 n个人排队到 1个水龙头处打水,第 i个人装满水桶所需的时间是 ti,请问如何安排他们的打水顺序才能使所有人的等待时间之和最小?
样例
输入
7
3 6 1 4 2 5 7
输出
56
算法1
(贪心) $O(nlogn)$
贪心选择:谁花的时间少谁先打水, 即按照打水时间递增排序
正确性证明: 调整性证明,如果存在相邻两个同学不满足打水花费时间的递增排序,则交换后,总时间会减小
总时间计算公式: $t_1 * (n - 1) + t_2 * (n - 2) + … + t_{n-1}$
时间复杂度 O(nlogn)
- 排序的时间复杂度O(nlogn)
- 遍历一次求结果O(n)
Python 代码
n = int(input())
nums = list(map(int, input().strip().split()))
nums.sort()
ans = 0
for i in range(n):
ans += (n - i - 1) * nums[i]
print(ans)