L. 排队打水问题

传统题

1000ms

256MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

有 $n$ 个人到 $r$ 个水龙头去打水，他们装满水桶的时间 $t_1, t_2, \dots, t_n$ 为整数且互不相等。应如何安排他们的打水顺序，才能使所有人花费的总时间最少？

每个人花费的时间 = 他等待的时间 + 他自己打水的时间。总花费时间为所有人花费的时间之和。

第一行包含两个整数 $n, r$ ，分别表示人数和水龙头个数。

第二行包含 $n$ 个整数 $t_1, t_2, \dots, t_n$ ，表示每个人打水需要的时间。

一个整数，表示最少的总花费时间。

3 2
1 2 3

样例 1 解释

最优安排：水龙头 1 依次打水 $1, 3$ ；水龙头 2 打水 $2$ 。
第一个人花费 $1$ ，第二个人花费 $2$ ，第三个人等待 $1$ 后打水 $3$ 花费 $4$ 。
总花费时间 $= 1 + 2 + 4 = 7$ 。

7 4
234 78 54 33 123 43 87