贪心习题C：排队打水

不懂贪心思路的点这里：贪心算法是什么

                                                                   排队打水

问题描述

有n个人排队到r个水龙头去打水，他们装满水桶的时间为整数，应如何安排他们的打水顺序才能使每个人花费的时间的总和最少？

输入格式

第一行
第二行为n个人打水所用的时间

输出格式

一个整数，最少花费的总时间

样例输入 1

3 2
1 2 3

样例输出 1

7

样例输入 2

4 2                     
2 6 4 5

样例输出 2

23

第一步：

        我们可以看到，这道题它让我们求的是总时间

        我们在做这道题时需要一点数学基础：

        就是速度快的一定要安排在速度慢的前面，因为比如我们现在以一个水龙头来举例子 

        一共有n个人，他们需要的时间分别是a1,a2……,an

        并且满足a1

        那么，我们把时间长的排在前面的话，需要等待的时间就是:n*an+(n-1)*a(n-1)+……+1*a1

        如果把时间短的安排在前面，需要等待的时间就是：1*an+2*a(n-1)+……+n*a1

        明显2式要比1式的结果少，所以把时间短的排在前面是最优的选择

      结论一：

                一定要把速度快的排在前面

        我们假设有两个水龙头，那些人的时间分别是1、2、3、4、5       

        那么，我们把接水速度为1的人安排在第一个水龙头

      假设一：

                速度为2的人要在速度为一的人的后面

                那么以此类推，速度为3的人要安排在速度为2的人后面

                速度为4的人就要在第二个水龙头5

                速度为5的人就要站在速度为4的人后面

               一号水龙头：

                         速度为1的人要等1分钟，速度为2的人要等1+2=3分钟，速度为3的人要等1+2+3=6分钟，加起来就是1+3+6=10分钟

                二号水龙头：

                          速度为4的人要等4分钟，速度为5的人要等4+5=9分钟，一共需要4+9=13分钟

                总时间：

                          一号水龙头需要10分钟，二号水龙头需要13分钟，一共需要10+13=23分钟

        假设二：

                  将速度为2的人排在第二个水龙头上，

                  将速度为3的人就要排在第1个人的后面，

                  速度为4的人安排在速度为2的人的后面                   

                  速度为5的人安排在速度为3的人后面

                一号水龙头：

                        速度为1的人要等1分钟，速度为3的人要等1+3=4分钟，速度为5的人要等1+3+5=9分钟

                 二号水龙头：

                         速度为2的人要等2分钟，速度为4的人要等2+4=6分钟

                  总时间:

                         一号水龙头需要9分钟，二号水龙头需要6分钟，一共需要9+6=15分钟

        比较两种假设：

                     明显假设一比假设二要慢一些，那这是为什么呢？

                     因为让速度慢的人站在一起，太浪费时间了！

            那么我们得到一个结论，要速度快，速度慢，速度快……这样的规律排在水龙头后面，才能使时间最少

第二步：

            临项交换法：慢的排前面，前面证明过了，明显不对，不在这里再解释一遍

第三步：         AC代码：

#include
#define MAX 1001
using namespace std;
int main()
{
	int n,r,sum=0;
	int a[MAX],b[MAX];
	memset(b,0,sizeof(b));
	scanf("%d%d",&n,&r); 
	for(int i=0;i 
上一篇：贪心习题B：拼数