排队打水问题（贪心算法）c++

有n个人排队到 r 个水龙头去打水，他们装满水桶的时间 t1, t2, …,tn 为整数且各不相等，应如何安排他们的打水顺序才能使他们花费的总时间最少？每个人打水的时间 = 排队的时间 + 实际打水的时间，本题假设一个人打好水，排在他后面的人接着打水的这个切换过程不消耗时间。比如，有2个人A和B，他们打水的时间分别是3和2，只有1个水龙头，这时，如果A先打水，B后打水，那么A和B打水的时间分别为3

BOTTLE平

1306人浏览 · 2024-10-07 18:22:05

BOTTLE平 · 2024-10-07 18:22:05 发布

题目描述

有n个人排队到 r 个水龙头去打水，他们装满水桶的时间 t1, t2, …,tn 为整数且各不相等，应如何安排他们的打水顺序才能使他们花费的总时间最少？

每个人打水的时间 = 排队的时间 + 实际打水的时间，本题假设一个人打好水，排在他后面的人接着打水的这个切换过程不消耗时间。
比如，有2个人A和B，他们打水的时间分别是3和2，只有1个水龙头，这时，如果A先打水，B后打水，那么A和B打水的时间分别为3、3+2（B排队3分钟）。

因此，所有人打水的总时间就是每个人的打水时间及每个人的排队时间的总和。

输入描述

第1行，两个整数n(1<=n<=500)和r(1<=r<=100)。
第2行，n个正整数t1,t2,…,tn，(1<=ti<=1000)表示每个人装满水桶的时间。

输出描述

1行，一个正整数，表示他们花费的最少总时间。

用例输入 1

4 2
2 6 4 5

用例输出 1

题解思路

题意简述

有n个人排队到r个水龙头去打水，每个人装满水桶的时间不同。需要安排他们的打水顺序，使得所有人花费的总时间最少。总时间包括每个人的打水时间和排队时间。

题目分析

贪心的核心是局部最优解，从而达到全局最优解。而局部最优解显然是打水时间短的人应该先打水

为了使总时间最少，我们需要尽量减少排队时间。显然，打水时间短的人应该先打水，这样可以减少后面人的排队时间。因此，我们可以对所有人的打水时间进行排序，然后依次分配到各个水龙头。

具体步骤

对所有人的打水时间进行升序排序。
使用一个数组sum来记录每个水龙头的当前累计时间。
依次将排序后的打水时间分配到当前累计时间最小的水龙头上。
最终，所有水龙头的累计时间之和即为最少总时间。

时间复杂度

排序的时间复杂度为O(n log n)。
分配时间的时间复杂度为O(n)。
因此，总的时间复杂度为O(n log n)，对于n最大为500的情况，这个复杂度是可以接受的。

代码实现

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n,m,sum=0;
    int a[100001];
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    sort(a+1,a+n+1); 
    for(int i=1;i<=n;i++)
    {
        if(i>=m+1)
        {
            a[i]=a[i]+a[i-m];
        }
        sum=sum+a[i];
    }
    cout<<sum;
    return 0;
}

所以你学会了吗？^0^