贪心算法-排队打水

数据结构与算法第九章基础算法贪心算法-排队打水

一、基本概念：
所谓贪心算法是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是某种意义的局部最优解。

二、基本思路：
1、建立数学模型来描述问题。
2、把求解的问题分成若干个子问题。
3、对每一子问题求解，得到子问题的局部最优解。
4、把子问题的解局部最优解合成原来解问题的一个解。

三、适用问题：
贪心策略适用的前提是：局部最优策略能导致产生全局最优解。

四、经典例题：

1、排队打水问题
有n个人排队到r个水龙头去打水，他们装满桶的时间为t₁,t₂,…..,t_n。为整数且各不相等，应如何安排他们的打水顺序才能使他们总共花费的时间最少？
输入样例：
4 2
2 6 4 5
输出样例
23

#include <cstdio>
#include <algorithm>
using namespace std;

int a[100]={0},v[100]={0};
int main(){
    int n,r,sum=0;
    scanf("%d%d",&n,&r);
    for (int i = 0; i <n; i++)
            scanf("%d",&a[i]);
    
    sort(a,a+n);
    for (int i = 0; i < n; i++)
    {
        sort(v,v+r);
        sum+=v[0]+a[i];
        v[0]+=a[i];
    }
    printf("%d",sum);
}

洛谷：P1223