【贪心】----排队打水
一、基础版排队打水
【题目描述】
学校里有一个水房，水房里一共装有m 个龙头可供同学们打开水，每个龙头每秒钟的供水量相等，均为1。
现在有n 名同学准备接水，他们的初始接水顺序已经确定。将这些同学按接水顺序从1到n 编号，i号同学的接水量为wi。接水开始时，1到m 号同学各占一个水龙头，并同时打开水龙头接水。当其中某名同学j完成其接水量要求wj后，下一名排队等候接水的同学k马上接替j 同学的位置开始接水。这个换人的过程是瞬间完成的，且没有任何水的浪费。即j 同学第x 秒结束时完成接水，则k同学第x+1 秒立刻开始接水。若当前接水人数n′不足m，则只有n′个龙头供水，其它m−n′个龙头关闭。
现在给出n名同学的接水量，按照上述接水规则，问所有同学都接完水需要多少秒。
【输入描述】
第1 行2 个整数n 和m，用一个空格隔开，分别表示接水人数和龙头个数。
第2 行n 个整数w1、w2、……、wn，每两个整数之间用一个空格隔开，wi 表示i 号同学的接水量。
【输出描述】
只有一行，1 个整数，表示接水所需的总时间。
【输入样例1】
5 3 4 4 1 2 1
【输出样例1】
4
【输入样例1说明】
第1 秒，3 人接水。第1 秒结束时，1、2、3 号同学每人的已接水量为1，3 号同学接完水，4 号同学接替3 号同学开始接水。
第2 秒，3 人接水。第2 秒结束时，1、2 号同学每人的已接水量为2，4 号同学的已接水量为1。
第3 秒，3 人接水。第3 秒结束时，1、2 号同学每人的已接水量为3，4 号同学的已接水量为2。4 号同学接完水，5 号同学接替4 号同学开始接水。
第4 秒，3 人接水。第4 秒结束时，1、2 号同学每人的已接水量为4，5 号同学的已接水量为1。1、2、5 号同学接完水，即所有人完成接水。
总接水时间为4 秒
【样例输入2】
8 4 23 71 87 32 70 93 80 76
【样例输出2】
163
【数据规模】
1≤n≤10000，1≤m≤100且 m<=n;
1≤wi≤100
【分析】
1.不要想的太复杂，不是排队接水(贪心)那种题。
2.开始的队伍已经排好（顺序已经固定），我们只要确定下个人去替代接完水的人的位置。
3.当队伍中有的人接完水后，下一个来接替的人的位置一定是当前队伍中接水最快的那个。
4.noip t2 的难度，没有必要用数据结构
5. 第m位同学接水，下一名同学是m+1
【思路1】
纯暴力模拟，按照时间和总接水量模拟
#include<bits/stdc++.h> using namespace std; int n,m,t; //定义n个人，m个水龙头,时间 int w[10005]; //存储每个人的接水量 int next,sum; //下一个接水的人的编号,总接水量 int main() { cin>>n>>m; next=m+1; //有m个水龙头，就有m个人接水，下一个一定是m+1号 for(int i=1;i<=n;i++) { cin>>w[i]; sum+=w[i]; //先把所有人的接水量都加起来 } //按接水量模拟 while(sum!=0) //当还没有接完水的时候继续循环 { for(int i=1; i<=m; i++) //枚举m个水龙头 { if(w[i]>0) //在这个水龙头的人的水没接完 { w[i]--; //接水量减1 sum--; //总量减1 } if(w[i]==0) //在这个水龙头的人接水完了，下个人跟上 { w[i]=w[next]; //下一个人接替上 w[next]=0; //重置为0 if(next!=n) next++; // 不到最后一个人就更新下一个人的编号 /* 上面两行代码要一块分析，假如最后三个水龙头的水量分别是 5，4，3 当三秒过后，3号水龙头接完，此时出现w[i]=0, 此时已经没有人可以替换了， 因为人都用完了，next值不会加1，那么w[i]还是保留最后一个人的接水量， 然后就死循环了，所以这个地方首先就是将 w[next]清空，防止出现死循环的 现象。 */ } } t++; //累计时间 } cout<<t; return 0; }【思路2】
因为每次被替换下来的一定是当前在水龙头队列里接水的最小一个或几个人，那么我们把找出最小的，把他替换掉。
#include<cstdio> int n,m,ans,w[105];//注意 不要以为n是水龙头的个数 int main() { scanf("%d%d",&n,&m); for(int i=0; i<m; i++) { scanf("%d",&w[i]); if(ans<w[i]) ans=w[i]; //找到最小值 } int minn,step,tmp; for(int i=m; i<n; i++) { minn=1e9; for(int i=0; i<m; i++) if(minn>w[i]) { minn=w[i]; //找到最小值 step=i; //记录位置 } scanf("%d",&tmp); //将下一个同学补上 w[step]+=tmp; if(ans<w[step]) ans=w[step]; //更新答案 } printf("%d\n",ans); return 0; }二、进阶版排队打水
【题目描述】
有n个人排队到r个水龙头去打水，他们装满水桶的时间t1，t2，…，tn为整数且各不相等，应如何安排他们的打水顺序才能使他们总共花费的时间最少？
【输入描述】
第一行n，r (n<=500,r<=75)
第二行为n个人打水所用的时间Ti (Ti<=100)；
【输出描述】
最少花费时间
【样例输入1】
3 2 1 2 3
【样例输出1】
7
【样例输入2】
4 2 2 6 4 5
【样例输出2】
23
【题目分析】
(1)题目描述比较坑，有一个非常重要的点没有告知：
接水的总时间=每个人接水的时间之和
每个人接水花费的时间=每个人接水的时间+等待时间
(2)我们是已经知道了每个人的接水的时间，现在的主要目的是如何给他们排队，让总时间最少。
样例1的解释，一共3个人，2个水龙头。
策略一：先让花费时间最少的两个人先去。
这里第一名同学需要花费了1分钟，第二名同学需要花费了2分钟。此时第三位同学还没有安排，但是已知第三名同学接水需要3分钟，如果第三位同学在2号水龙头，那么他将花费3+2(2是他在2号水龙头等待的时间)，比他在1号水龙头额外多花1分钟。显然，3号同学应该在1号水龙头后等待接水，这样总体接水的时间是最少的。
1+2+(3+1)=7
策略二：让花费时间的多的先去。
我们让花费时间最多的两位同学先去，这个时候，最后一位同学有如果在2号水龙头，他将花费2+1分钟。如果去1号水龙头，他将花3+1分钟。显然，在策略二中最少的排队接水时间应该是3+2+(2+1)=8分钟。
综上来说，对于样例1，应该选择策略一，将需要排队人总是安排到当前水龙头花费时间最少的那个。
同样，样例2，也可以有类似的解释。
(3)我们要求一个总时间，某个人的花费时间是排在当前这个水龙头的总时间+ 这个人接水的时间。
【参考代码1】
对于测试数据
4 2 2 6 4 5
的过程表示是
排队打水的数学推导过程
要让平均排队时间最小，就要让打水快的人往前排
证：
设有n个人打水，每个人的打水时间分别为 x_1,x_2,x_2,…,x_nx1,x2,x2,…,xn
则打水时间总和为x_1*(n-1)+x_2*(n-2)+…+x_{n-1}*1+x_n*0x1∗(n−1)+x2∗(n−2)+…+xn−1∗1+xn∗0
要让打水总时间最小，就要让x_1<x_2<…<x_nx1<x2<…<xn
所以我们可得
1.排序，对输入进行排序，使其变成x_1<x_2<…<x_nx1<x2<…<xn这个序列
2.累加时间，如果用x_1*(n-1)+…+x_{n-1}*1+x_n*0x1∗(n−1)+…+xn−1∗1+xn∗0会比较麻烦，我们换一个方式,令x_0=0x0=0 我们求x_0+(x_0+x_1)+…+(x_0+x_2+…+x_{n-1})x0+(x0+x1)+…+(x0+x2+…+xn−1)
3.把加完的时间除以n，再把x_1,x_2,…,x_nx1,x2,…,xn和时间输出
总等待时间：t1+(t1+t2)+(t1+t2+t3)+……+(t1+t2+t3+……+tn)
所以要把接水时间较少的放在前面
三、相关题目
【题目描述】
有n个人在一个水龙头前排队接水，假如每个人接水的时间为Ti，请找出这n个人排队的一种顺序，使得n个人的平均等待时间最小。
【输入描述】
第一行为一个整数n。第二行n个整数，第i个整数Ti表示第i个人的等待时间Ti。
【输出描述】
输出有两行，第一行为一种平均等待时间最短的排队顺序；第二行为这种排队方法下的平均等待时间。(结果保留小数点后两位)
【样例输入】
10 56 12 1 99 1000 234 33 55 99 812
【样例输出】
3 2 7 8 1 4 9 6 10 5 291.90
(adsbygoogle = window.adsbygoogle || []).push({});