算法设计与分析 SCAU17964 水桶打水

17964 水桶打水

时间限制:1000MS 代码长度限制:10KB
提交次数:25 通过次数:9

题型: 编程题 语言: G++;GCC;VC;JAVA

Description

有n个人（n<100000）带着大大小小的水桶容器（每人一个水桶）排队到r个（r<1000）水龙头打水，
他们装满水桶的时间分别是t1，t2，……，tn，并且时间是整数且各不相同，应如何安排他们的打水顺序
才能使他们花费的总时间和最少？

输入格式

分两行：第一行人数n和水龙头数r；第二行为t1 t2 …… tn。

输出格式

最少的所有人的总花费时间和。

输入样例

4 2
2 6 4 5

输出样例

23

解题思路

贪心算法

每个人整个打水的时间为：本人等待时间 + 本人实际充水的时间；
而本人的等待时间又为：排在 本人之前所有人 的充水时间之和。

1. 本题目标是所有人打水花费的总时间和最小。
2. 由于排在越前面的人，他的充水时间计算次数就越多，
3. 因此充水时间 越小的人排在前面 可使所有人打水花费的总时间和越小，所以用贪心法解答。

算法思路

（1）将输入的充水时间按从小到大排序；
（2）将排序后的时间按顺序依次放入最早完成的水龙头的排队队列中，同时使用 greedy 数组记录该水龙头下一个使用者需等待时间
（3）统计，输出合计后的完成时间和，即每次都进行 res += greedy[i % r] + a[i] 即可（该水龙头前面的人使用时间 + 现在使用的人需使用时间）

更多注释可查看下方的完整代码中，有助于理解。

代码如下

#include 
#include 
#include 

/*
4 2
2 6 4 5
*/

using namespace std;

int main()
{
    int i, n, r, res = 0;
    int a[100001]; // 记录各个人需要花费的打水时间
    int greedy[100001]; // 用于记录每个水龙头的占用时间，共 r 个水龙头
    memset(greedy, 0, sizeof(greedy));

    cin >> n >> r;

    for(i = 0; i < n; i++) {
        cin >> a[i];
    }

    sort(a, a + n);

    for(i = 0; i < n; i++) {
        res += greedy[i % r] + a[i]; // 该水龙头前面的人使用时间 + 现在使用的人需使用时间
        greedy[i % r] += a[i]; // 更新该水龙头下一个使用者需等待时间
    }

    cout << res << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34