贪心算法-排队打水

经典算法

贪心算法-排队打水

阅读量: 96 编辑

有 N 个人排队到 R 个水龙头去打水，他们装满水桶的时间为整数 T1，T2，...，Tn，且各不相等，应如何安排他们的打水顺序才能使他们花费的总时间最少？

【贪心策略】

T越小的人，打水越要靠前。（每个人 T总时间 = T每个人打水时间 + T每个人等待时间）

【输入描述】

输入两行。第一行输入 N 个人，和水龙头数量 R；第二行输入每个水桶装满水的时间T。

【输出描述】

输出一行。输出打水总的花费时间。

【输入样例】

4 2
2 6 4 5

【输出样例】

【参考程序】

// 爱码岛编程
#include <bits/stdc++.h>
using namespace std;

// 每个人接水时间
int t[10001];

int main() {
    //人数，水龙头数
    int N, R, Sn = 0;
    cin >> N >> R;

    for (int i = 1; i <= N; i++)
        cin >> t[i];

    sort(t + 1, t + N);

    for (int i = 1; i <= N; i++) {
        if (i > R) {
            //接水时间和等待时间累加
            t[i] = t[i] + t[i - R]; //分组
        }
        Sn += t[i]; //累加
    }

    cout << Sn << endl;

    return 0;
}