139 贪心 - 排队打水

主要内容

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;
}