主要内容 #

1. 问题描述
2. 算法思路
3. 参考程序

1. 问题描述 #

有n个人排队到r个水龙头去打水，他们装满水桶的时间t1、t2………..tn为整数且各不相等，应如何安排他们的打水顺序才能使他们总共花费的时间最少？
输入格式
第一行n，r (n<=500,r<=75)
第二行为n个人打水所用的时间Ti (Ti<=100)；
输出格式
最少的花费时间
样例输入
3 2
1 2 3
样例输出
7

2. 算法思路 #

这道题最后要求
花费的时间=每个人接水的时间+每个人排队等待的时间
确定了这个就很好求了
这个题的贪心策略：
因为每个人的接水时间已经是固定的了，那么要确定最少的花费时间
就取决于让每个人排队等待的时间最少
这样让接水时间少的人先接,就能保证后面排队的人用时最短。
(1)将输入的时间按照从小到大排序；
(2)将排序后的时间按找顺序依次放入每个水龙头的队列中；
(3)统计，输出答案。

3. 参考程序 #

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int main()
{
    int n,r,sum=0;     //人数，水龙头数
    int s[5000],arr[5000];  //装满水桶的时间
    memset(s,0,sizeof(s));  //初始化
    cin >> n >> r;
    for(int i=1; i<=n; i++)
        cin >> arr[i];
    sort(arr+1,arr+1+n);  //从小到大排序
    int k=0;
    for(int i=1;i<=n;i++)
    {
        k++;
        if(k==r+1) //r人一组,第r+1个人回到第一个龙头
            k=1;
        s[k] += arr[i];//加上等待时间
        sum += s[k];//累加
    }
    cout << sum << endl;
    return 0;
}