贪心算法初探

一、什么是贪心算法

贪心在我们字典里面往往是一个负面词汇，比如我们说一个人太贪心，往往是形容这个人目光短浅，只顾眼前，而没想到后面更大的损失。然而贪心算法或贪心思想采用的贪心策略，保证每次操作都是局部最优的，从而使最后的结果也是全局最优的
并不是所有问题都适用贪心算法，对于某些不适用的问题采用贪心算法时，往往得不到想要的结果。
以后讲到动规会提到

咱们来举一个小例子，来说明这个问题。

小乐和小博所在的乐博机器人学校，为同桌的小朋友准备了3个苹果，苹果2大一小,大的苹果价格5块钱，小的价格3块钱。小苹果吃起来所用的时间短，大苹果吃完所用的时间长，老师规定只有吃完一个苹果后，才能拿第二个，请问如何选才能使自己吃到更多价值的苹果呢？

小乐想，如果由我先选的话，那我就要先吃那个小的，等吃完后，我再吃那个大的。这样我就能吃到两个苹果，价值是8块钱。
如果我先选大的，而小博也选择小的话，那吃完后，盘子里就没有苹果了，这样只吃一个大苹果，价值是5块钱。

如果你是小乐的话，为了吃掉更多价值的苹果，你会选择跟他一样的策略吗？

贪心讲策略
从这个例子可以看出，贪心并不是每次都选择大的，而是讲究策略的。这个策略的目的就是为了使得最终得到一个最好的结果。
所以我们学习贪心算法，也就是重点学习贪心策略，也即针对不同的问题，采用什么样的贪心策略，才能得到最好的结果。

二、渡河问题

题目：
现在有一群人，到了一条河旁边，想要过河，但船只有一条，一次最多能载两个人，开到了对面还需要一个人负责把船开回来，而且若多人坐船，速度还是由慢的一个决定，现在求如何分配坐船，使总时间最短。
输入:
第1行输入n，第2行输入n个数，表示每个人过河的时间。
输出:
输出一行数据，每行1个数，表示每组过河最少时间。
样例输入：
4
1 2 5 10
样例输出：
17

分析：

方法一，暴力搜索DFS
假设有a,b,c,d四个人渡河，第一次渡河从4个人中选取2个人渡河，有6种方法，从对岸2个人中再选取1人返回有2种方法，然后再从起点处的3人中选取2人，有3种方法，最后从对岸2人中选取1人返回，有2种方法，整个过程有623*2=72种方法，从这72种方法找出最快的一种。显然，用这种方法效率太低!

方法二：利用贪心思维，每次让最快的人带最慢的人渡河，耗时19S

我们发现这种策略并不是最优的

假设现在有k个人要渡河，令往返各2次为一轮
明显经过一轮后，河岸少了2人渡河，最佳安排有以下两种情况：


code:

#include<bits/stdc++.h>
using namespace std;
int n,a[1000100],ans=0;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    while(n>3)
    {
        if(a[2]*2+a[1]+a[n]>=a[1]*2+a[n-1]+a[n])
 /*
 第(1)种情况是两个速度最快的过河，再由第一个人将船送回，
 再两个速度最慢的过河，由最快的将船送回，
 时间为a[2]+a[2]+a[n]+a[1]；
 第(2)种情况是最快的反复跑所用时间为a[1]*2+a[n-1]+a[n]；
 */
        ans+=a[1]*2+a[n-1]+a[n];
        else ans+=a[2]*2+a[1]+a[n];
        n-=2;//每次加两个人的过河时间
    }
    //找关系可得最后三个人的时间为三者时间想加，可以自己推算。
    if(n==3) ans+=a[1]+a[2]+a[3];
    if(n==2) ans+=a[2];//最后两个人的时间即为速度慢的人所用的时间。
    if(n==1) ans+=a[1];// 最后一人过河时间就是他的过河时间。
    cout<<ans;
    return 0;
}

贪心与区间问题

通过贪心算法来解决区间问题，大概分以下几类：

1. 最大区间和问题
2. 不相交区间问题
3. 区间选点问题
4. 合并区间问题
5. 区间覆盖问题

一、求最大区间和

我们最开始想到的方法是使用深搜的方法，把所有的子段都列出来，再计算子段的和，然后通过打擂台的方式就能求出最大值，但是这样的方法效率极低，我们应该考虑其他方法。

贪心策略分析：
我们想一个问题，我们要求得这个最大区间和，区间左面的数字若是存在，那么一定是一个负数，负数我们不取，右面也是一样。
我们声明两个变量，一个ans,一个是区间和s，遇到s>ans时，就让ans=s
这样一个O(n)的时间复杂度就可以解决这个问题。

题目：
输入一个正整数n，代表一个数列有n个元素，请试着求出最大的子段和。
输入：
一个正整数n，第二行有n个整数，用空格分开。
输出：
最大区间和
输入样例：
8
-1 -3 2 3 -4 6 7 -5
输出样例：
14

code

#include<iostream>
using namespace std;

int main(){
	int n,x,ans=0,s=0;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>x;
		s+=x;
		if(s>ans)
			ans=s;
		if(s<0)
			s=0;
	}
	cout<<ans;
} 

我们发现当n个整数全是负数的时候就不用于此方法，例如洛谷P1115 最大子段和,我们之后学习动态路径规划（dp) 的时候再进行详细讲解

二、不相交区间问题

所谓不相交问题，就是有多个区间，这些区间是有交集的，如何避免交集的情况下选择更多的区间问题。我们现实生活中也经常会有这样的情况出现，比如下面的一道题。

题目：
乐博机器人学校要举行一场RSC比赛，在比赛前一般各个小队都要进行排练，为此乐博提供了一间活动室，可以供各参赛小队排练使用，乐博安排柚子同学负责安排活动室的使用，于是柚子同学要求各小队将自己排练开始时间和结束时间给提报上来。
当柚子同学收到这些活动的时候，有点头疼，因为有的小队使用的时间长，有的小队使用的时间短。关键问题是小队之间使用时间上发生了冲突，即A小队还没有结束，B小队的排练时间就开始了。活动室要求必须一个小队用完才能让另一个小队使用。即A小队4点结束，B小队就不能早于4点开始使用，必须要>=4点才可以。
各个小队的排练时间已经上报不能协调更改了，为了尽量让更多的小队能够完成排练，那只能在活动安排上下功夫，柚子同学是参加过信奥赛的，对算法非常了解，请算出一个活动室最多能安排多少小队排练。
输入：
第一行，一个整数n，代表有n个小队
后面有n行，每行两个整数，用一个空格分开，分别代表每支小队的开始和结束时间
输出：
一个整数，表示活动室能够安排下的最多排练小队数量
样例输入：
4
1 5
1 2
3 4
5 6
样例输出：
3

分析：

这是一个典型的不相交区间问题，而且各个区间是闭区间，即不允许有边界点有重叠，如下图所示

1. 如果选择了1队，则后面只能选择4队；如果选择了2队，则还能选择3队，4队，这样就有3支队伍可以使用活动室
2. 为了能够选择更多的队伍，我们需要选择尽量活动结束时间靠前的，所以我们先根据其结束时间进行一个升序排列。那么最前面的一定是最早结束的。如下图所示
   
3. 排序后，进行如下循环处理：
   设置第一个变量t = -1，循环从1~n队，每到一队，就看这一队的开始时间s[i]，判断s[i]是否>=t，若是就将t设置为该队的结束时间，并cnt++

• s[i]:第i队的开始时间
• e[i]:第i队的结束时间
• cnt：计数器，最多几个小队使用活动室，即本题答案

for(int i=1;i<=n;i++){
	if(s[i]>=t;
		t=e[i];
		cnt++;
}

code:

#include<iostream>
using namespace std;

int main(){
	int s[1001],e[1001],n,t=-1,cnt=0;//也可以使用结构体 
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>s[i]>>e[i];
	//冒泡排序，学到结构体建议使用结构体排序 
	for(int i=1;i<=n;i++){
		for(int j=i+1;j>1;j--){
			if(e[j]<e[j-1]){
				//注意：开始时间和结束时间要一起排， 不然顺序就乱了
				swap(e[j],e[j-1]);
				swap(s[j],s[j-1]); 
			}
		}
	}
	for(int i=1;i<=n;i++){
		if(s[i]>=t){
			t=e[i];
			cnt++;
		}
	}
	cout<<cnt;
} 

三、区间选点问题

选择最少的点，穿过所有区间。先来看下面这道题

题目：
乐博机器人学校所在的城市盛产一种蔬菜，这种蔬菜很奇怪只要下雨就会减产。为了避免这种情况。乐博机器人学校的小朋友研制了一种装置，称为“穿云箭”，可以将天上的云打散，这样就不会下雨了。
穿云箭只能向上发射，且这支箭可以穿透其上方的所有云朵。有些云朵只要跟这支箭擦边而过也会被打散，比如某云朵是[3,5]而发射的箭穿过了5，此云朵也会被打散。
穿云箭可以沿着轨道左右移动。
由于每一支箭都造价较高，所以要尽量节约使用。
现给出各云朵的左右端点，请问最少可以用多少支箭可以完成任务。
输入：
第一行一个正整数n，代表云朵的数量
下面有n行，每行两个整数，中间用空格分开。分别代表其左、右端点。
输出：
一个整数，表示可以完成任务的最少箭数
样例输入：
4
1 6
2 5
3 6
5 6
样例输出：
1

分析：

1. 想要花费的箭最少，则每支箭所要穿过的云就要尽量多，所以选择在哪个点发射就是一个关键问题。
2. 如何确定在哪个位置发射呢。我们还是先根据每朵云的左端点来进行升序排序
   
3. 排序后进行如下循环处理：
   设置一个变量t = -1,循环1~n朵云，每到一朵云，就看这朵云的左端点s[i]，判断是否s[i]>t，若是就将t设置为该云的右端点，并将cnt++

• s[i]:第i朵云的左端点
• e[i]:第i朵云的右端点
  -cnt:计数器，最少几支穿云箭完成任务，即本题答案

for(int i=1;i<n;i++){
	if(s[i]>t){
		t=e[i];
		cnt++;
	}
}

code:

#include<iostream>
using namespace std;

int main(){
	int s[1001],e[1001],n,t=-1,cnt=0;//也可以使用结构体 
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>s[i]>>e[i];
	//冒泡排序，学到结构体建议使用结构体排序 
	for(int i=1;i<n;i++){
		for(int j=i+1;j>1;j--){
			if(s[j]<s[j-1]){
				//注意：开始时间和结束时间要一起排， 不然顺序就乱了
				swap(e[j],e[j-1]);
				swap(s[j],s[j-1]); 
			}
		}
	}
	for(int i=1;i<=n;i++){
		if(s[i]>=t){
			t=e[i];
			cnt++;
		}
	}
	cout<<cnt;
} 

四、合并空间

所谓合并空间，就是将重叠的区间进行合并。

题目：
给定n个闭区间，对重叠的区间进行合并。
输入：
第一行一个整数n，代表区间的数量。
下面有n行，每行两个整数，中间用空格分开，分别代表区间的左右端点。
输出：
第一行输出一个整数，表示有几个区间
接下来每行一个区间，两个整数，用空格分开。
样例输入：
5
1 5
2 3
2 6
7 9
8 10
样例输出：
2
1 6
7 10

分析：

合并区间与区间选点问题具有相似性

code:

#include<iostream>
using namespace std;

int main() {
	int s[1001],e[1001],n,t=-1,cnt=0;//也可以使用结构体
	cin>>n;
	for(int i=1; i<=n; i++)
		cin>>s[i]>>e[i];
	//冒泡排序，学到结构体建议使用结构体排序
	for(int i=1; i<n; i++) {
		for(int j=i+1; j>1; j--) {
			if(s[j]<s[j-1]) {
				//注意：开始时间和结束时间要一起排， 不然顺序就乱了
				swap(e[j],e[j-1]);
				swap(s[j],s[j-1]);
			}
		}
	}
	t=e[1];
	cout<<s[1]<<" ";
	for(int i=1; i<=n; i++) {
		if(s[i]>t) {
			cout<<t<<endl;
			cout<<s[i]<<" ";
		}
		t=e[i];
	}
	cout<<t;
}

五、区间覆盖问题

题目：
现有含n个元素的数组a，玩家从第一个元素出发，可以向前跳的是1~a[1]步，如果某元素是0，则NO代表不能向前走，这种元素称之为“陷阱”，如果你不能跳过陷阱，则代表无法到达最后一个元素，也就是到达不了终点。
输入：
第一行，一个数字n,5<=n<=10000
第二行有n个数字，中间用空格分开。数字为[0~20]
**输出：**YES
如果玩家能够到达目的地，请输出“YES”，否则输出“NO”
样例输入：
6
4 3 2 1 0 5
样例输出：
“NO”

分析：

1. 根据样例可知，如果跳的步数无法跨越陷阱，那是无论如何都过不去的。
   
2. 能够跨越陷阱的情况是什么样子的？，我们来看下面的这张图
   

由于以上两张图我们发现，我们只要从第一个元素开始，不断地向后遍历，只要在遍历的过程中有任何一个点，他的跳跃范围包含了目标点位置，就算是能够到达。

code:

#include<iostream>
using namespace std;

int main(){
	int a[10005],n,t=0;
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	for(int i=1;i<=n;i++){
		//可以跳到的最大范围
		if(i+a[i]>t)
			t=i+a[i];
			//若最大范围包含目标点
			if(t>=n){
				cout<<"YES";
				return 0;//找到了就不用再执行了 
			} 
			if(a[i]==0&&t==i){
				cout<<"NO";
				return 0;
			} 
	} 
	cout<<"NO";
} 

总结：

1. 区间和问题，遇到和是负数则舍弃，若是和是正数则保留继续向后找，一直到结束，便能统计出最大和是多少
2. 不相交区间最大问题，主要适用于某些活动举办时场所占用问题，要能够通过结束时间排序来找出最多的区间
3. 区间选点问题，是选出最少的点，而被更多的区间所包含，按左端点升序排列，之后从第1个区间最右侧的端点开始判断左端点小于此端点的区间，直到这些区间都被过滤后，再进入下一个区间，重复以上步骤。
4. 区间合并，是合并相交区间的问题，判断相交然后进行合并即可。
5. 区间覆盖问题，需要注意不同区间的覆盖范围，如果范围包含目标点，则证明可以过去，否则过不去。

贪心与趋势问题

趋势大致有以下几种：

1. 上下波动的趋势
2. 单调递增的趋势，
3. 单调递减的趋势
4. 双向趋势处理

以上每一种问题，都可以解决现实生活中的相关问题。

一、上下波动的趋势

首先，我们先来看看什么是波动序列。给定一个序列，这个序列有大有小，在不排序的情况下，如果将这一些数字进行连线，其一定是一个上下左右波动的曲线。比如说，给定的数列是[1,3,2,4,1,3,1]。
我们将给定的数字作为y值，其数列的下标作为x值，则其所有点的连线，是一个上下波动的折线。

在这个折线图上，你会发现一个特点，就是他一直在上下波动，绝对不会出现连续的向上，也不会存在连续的向下。像这样的序列我们称为波动序列或摆动序列。

题目：
给定一个有n个元素的数列，求其最长的波动子序列，要求保留其原来的上下峰值节点的数据。
输入：
一个正整数n，不超过100，
之后跟着n个整数。
输出：
一行，满足要求的子序列，每个数字用空格隔开。

分析：

对于这道题目，只要保留原来的上下波动峰值节点，就恰好满足这个题目的要求

看上面的图，图中的蓝色的点就是波动峰值节点，而红色的点就是非波动峰值节点。
我们要的是保留的就是转折点的最长波动子序列。

如何判断一个节点是不是转折点

1. 从上图来看有以下两种情况：这个点得是驻点（左高右低，左低右高）
2. 如果相邻两数相等的情况怎么判断？如下图所示

以上两张图，如果存在相邻两节点数值相同，若两点都存在上升或下降趋势的中间点，如左图所示，则都不能作为转折点。
如果存在于转折点上，因为数值都是相同的，则取左面还是右面并没有什么影响。

我们分析判断完了，程序应该怎么写？如何对上面的两种情况进行判断？

• 我们声明两个变量,记作：cur和pre
• cur：当前差值，即当前数字被后一个数字所减的差值。
• pre：上一个差值，即上一个转折点出现时的差值
• if(cur > 0 && pre <= 0 || cur < 0 && pre >= 0
• 如果满足这种情况，认为是转折点，把当前的差值赋值给pre
• pre = cur
  
  

对于头尾两个节点怎么处理？
从题目来看，这两个节点无论如何都是存在于最长波动子序列中的。
对于首元素，我们上面的判断条件，无论如何都会将其包含进去的，除非后面的元素和他相等，若相同的转折点，我们默认取右面的，那就不会取首元素，但不影响我们取数。
对于尾元素，好像他没有cur这个差值，因为后面不存在一个元素去减他，所以我们的循环区间不会包含尾元素。但尾元素无论什么情况，都要保存进来，有以下原因：

1. 如果前面与之相等，我们默认取右面，他是最右面所以一定要取
2. 如果前面与之不等，不管是大还是小，则他一定是趋势的终点，所以也一定要取

code:

#include<iostream>
using namespace std;

int main() {
	int a[110],b[110],n,m=1;
	cin>>n;
	for(int i=1; i<=n; i++)
		cin>>a[i];
	int cur,pre=0;
	// 循环范围：首个数字~尾数的前一个数
	for(int i=1; i<n; i++) {
		//当前数与后一数的差值
		cur=a[i+1]-a[i];
		//判断条件
		if(cur>0&&pre<=0||cur<0&&pre>=0) {
			b[m++]=a[i];
			//把当前值赋值给pre，用于下一轮的前插值
			pre=cur;
		}
	}
	//无论如何，都要加上最后一个
	b[m]=a[n-1];
	//输出最长波动子序列
	for(int i=1; i<=m; i++)
		cout<<b[i]<<" ";
}

二、单调递增的趋势

题目：
乐博机器人学校举行跳槽市场活动，同学们会把自己平时不用的学习用品、图书、玩具等拿到学校来进行售卖，同学们会在这一天里购买自己喜欢的东西，也会将一些自己不用的东西卖掉，使闲置的物品最大化利用，以此为保护环境做出贡献，因为再造这些物品是需要消耗资源的。
小乐是一个非常有经商头脑的同学，他感觉可以将一些抢手的物品A买入卖出来赚取差价，但是老师也有规定，相同的物品手中只能有一个，不能手里还继续买。
于是小乐想从物品A低价时买，价高时卖出，但当活动结束时，无论如何也得把手里的物品换成钱。
现给出一个整数n，代表有n个时刻，下面一行n个数字，代表每个时刻A的价格，每个价格用空格分开。
问活动结束时小乐最多能赚多少钱？
输入：
第一行是一个正整数n,1<=n<=10000,
第二行是n个整数，每个整数用空格分开，10<=a[i]<=100
输出：
一个正整数，代表小乐赚到的钱
输入样例：
8
1 3 6 2 5 4 9 2
输出样例：
13

分析：

要使最后赚的钱最多，则每次交易必须要赚钱，交易次数要足够多
即：赚钱总和=每次赚的钱*交易次数
怎么求交易次数和每次赚的钱？
第1个时刻，因为手里没东西，所以肯定是只能买不能卖的，除此时刻之外的其他时刻假设都是可以卖的，那么所赚的钱就是这一时刻的价格 - 前一时刻的价格之差
我们求到这个差之后，将所有是正数的值相加求和，就是最后的结果。

code:

#include<iostream>
using namespace std;

int main(){
	int n,ans,t1,t2,cha;
	//获取时刻总数 
	cin>>n;
	//第一个时刻单价单独获取
	cin>>t1;
	//后面还要n-1个时刻
	for(int i=2;i<=n;i++){
		//获取时刻价格
		cin>>t2;
		//计算与前一时刻的差
		cha=t2-t1;
		//若差>0,则加到总和里面
		if(cha>0)
			ans+=cha;
		//将这次的价格给t1，作为下次的上次价格
		t1=t2; 
	} 
	cout<<ans;
} 

以上就是一个非常明显的贪心实例，就是把能赚的钱全赚了，亏钱的一次不要

三、单调递减趋势

题目：
输入一个高精度整数s，去掉其中任意m个数字按原左右次序组成一个新的正整数，求出给定的s和m，寻找一种方案使得剩下的数字组成新的数字最小。
输入：
s
m
输出：
最后剩下的最小的数
输入样例：
175438
4
输出样例：
13

分析：

假如要删除一个数字，那一定是从最高位开始找，如果最高位比后面的数大，则删除，否则留下。如此循环下去，自然剩下的数最小。

code:

#include<iostream>
using namespace std;

int main() {
	string s;
	int m;
	cin>>s>>m;
	int len=s.length();
	//循环删除m个位
	for(int i=0; i<m; i++) {
		//从最高位开始遍历
		for(int i=0; i<len-1; i++) {
			//后面的位小，则删除前面的
			if(s[i]>s[i+1]) {
				//后面每一位前移
				for(int j=i; j<len-1; j++)
					s[j]=s[j+1];
				break;
			}
		}
		len--;
	}
	//循环删除前导0
	int j=0,x=len;
	while(s[j]=='0'&&x>1)
		j++,x--;
	//输出
	for(int i=j; i<len; i++)
		cout<<s[i];
}

四、双向趋势处理

题目：
乐博机器人学校进行了信奥考试，老师根据每个孩子的评分决定分发一定的奖励，奖品是一种品味独特的糖。老师让所有的孩子都站成一排，希望每个学生都能分到至少1块糖，但是考分高的孩子，一定要比他相邻的同学分到的要多，至于多几块倒是无所谓，而对于考试成绩相同的相邻同学，就无所谓谁比谁多了。
由于这种唐=糖比较昂贵，所以老师希望尽量少的准备，请问老师要准备多少块糖呢？
输入：
第一行是一个整数n，代表有n位同学
第二行是n个整数，代表每个同学的评分
输出：
一个整数，代表老师要准备的糖的数量
输入样例：
6
1 0 2 2 3 2
输出样例：
9

分析：

1. 右边的孩子评分如果比左边的高，则其分的糖要多
2. 左边的孩子评分如果比右边的高，则其发呢的糖也要多
   所以分两步来处理就行了

code:

#include<iostream>
using namespace std;

int main() {
	int a[1000],b[1000],n,ans=0;
	cin>>n;
	for(int i=1; i<=n; i++) {
		cin>>a[i];
		b[i]=1;
	}
	//从左向右处理趋势
	for(int i=2; i<=n; i++)
		if(a[i]>a[i-1])
			b[i]=b[i-1]+1;
	//从右向左处理趋势
	for(int i=n-1; i>=1; i--)
		if(a[i]>a[i+1])
			b[i]=b[i+1]+1;
	//汇总求和
	for(int i=1; i<=n; i++)
		ans+=b[i];
	cout<<ans;
}

总结：

1. 对于上下波动的趋势，要明白这个趋势的特点，并能够进行判断，取得最长波动趋势
2. 对于单调趋势，同样要明白趋势的判断，并能够进行这一类趋势问题的应用处理，比如使数字最小的删数问题
3. 对于双向趋势的处理，要能够从左往右、从右往左来处理，以满足目标的需求。

贪心与排队问题

贪心与排队问题，大致分为以下几类：

1. 排一队，人耗最少。若有10个人，每人等1分钟，总等待时间，就相当于是10分钟的人耗。
2. 排多队，时间最快。若10个人排成5个队，最快完成时间，取决于最后完成的人。
3. 木桶理论，效用最大。木桶由多块木板组成，装水量取决于最短的木板，短板一词也由此而来。

一、排一队使人耗最少

题目:
排队打水，有n个同学去打水，因为每个同学的水壶容量不同，所以打水所用的时间也不同，现给出每个同学的打水等待时间。请你安排一种排》顺序，使得人耗最低。每个同学编号是按输入顺序从1开始编号。
请求出这个最低的人耗数量，以及平均的等待时间。
输入:
第一行一个正整数n，代表有n个同学。
第二行有n个正整数，代表每个同学的打水所用时间。
输出:
第一行，输出打水所用的最少总等待时间(若有10个人，每个等待1分钟，那么总等待时间就是10分钟)
第二行，输出最低平均等待时间(保留小数点后2位)。注意第1个人的等待时间是0。第三行，输出排队顺序，每个编号用空格分开。
样例输入：
5
8 7 15 12 10
样例输出：
84
16.80
2 1 5 4 3

分析：

1. 总等待时间，就是每个人的等待时间总和。第1个人是不用等待的。如果按照原来顺序，总等待时间如下:
   
   很明显，如果让1号先打水，则2号要等待8个时间单位，而如果让2号先打，则1号只要等待7个时间单位,等待时间就少了1待时间概念。
   符合题意的最少总等
   他们俩的交换，会对其它同学产生影响吗?很明显，对于3号~5号同学的等待时间，毫无影响。
   那么，也就是说，让快的先打水，慢的后打水，总等待时间一定最少。

2. 对学生的打水时间进行排序，使其按升序排列。然后再计算等待时间
   
   总等待时间变成了84，明显这样的策略是比直接打水要节省时间的。
3. 计算排队等待时间
   假设用数组c来存储等待时间，用数组a来存储每个同学的打水时间，
   则排队后在第i位同学的等待时间，c[i]=c[i-1]+a[i]。这里要能够理解清楚,因为下面在计算的时候，是从i=1到i<n结束

for(int i=1;i<n;i++){
	c[i]=c[i-1]+a[i];
	ans+=c[i];
}

code:

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

int main() {
	int a[1005],b[10005],c[10005],n,ans;
	cin>>n;
	for(int i=1; i<=n; i++) {
		cin>>a[i];
		b[i]=i;
	}
	//选择排序
	for(int i=1; i<n; i++) {
		int k=i;
		for(int j=i+1; j<=n; j++) {
			if(a[k]>a[j])
				k=j;
		}
		if(k!=i) {
			swap(a[i],a[k]);
			swap(b[i],b[k]);
		}
	}
	//第1个数是第2个人的等待时间，截至到n-1个数，是第n个人的等待时间
	for(int i=1; i<n; i++) {
		c[i]=c[i-1]+a[i];
		ans+=c[i];
	}
	double res=ans*1.0/n;
	printf("%d\n%.2lf\n",ans,res);
	for(int i=1; i<=n; i++)
		cout<<b[i]<<" ";
}

二、排多队使时间最快

这种问题就是常识性问题，关键在于代码的实现，先来看下面的题目：

题目:
学校里有一个水房，水房里一共装有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、w3…wn，每两个整数之间用一个空格隔开，wi表示i号同学的接水量。
输出：
输出只有一行，1个整数，表示接水所需要的总时间
输入样例1：
5 3
4 4 1 2 1
输出样例1：
4
输入样例2：
8 4
23 71 87 32 70 93 80 76
输出样例2：
163
提示：
输入输出样例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秒。

分析：

这道题目非常清晰，就是哪个队快就往哪个队放人,以最快完成的那一个，算完成时间。难点在于，如何实现遍历多个队伍，实现往最少的队伍里放人
其实分三步

1. 声明3个队伍，先将123号放到队伍里去。
2. 遍历3个队伍，看哪个队伍时间最少，就把第4个人放进去，以此类推，直到把所有人都放进去为止
3. 然后再看哪个队伍花的时间最长，就是最快完成时间了

code:

#include<iostream>
using namespace std;

int main() {
	int a[1005],b[10005],n,m,ans=0;
	cin>>n>>m;
	for(int i=1; i<=n; i++)
		cin>>a[i];
	int minx=0,minm=0;
	for(int i=1; i<=n; i++) {
		//遍历m个水龙头
		for(int j=0; j<m; j++) {
			//取最少的那个
			if(b[j]<minx) {
				minx=b[j];
				minm=j;
			}
		}
		//把人排到最快的队伍上
		b[minm]+=a[i];
		minx=b[minm];
	}
	//找出最后完成的队伍，其时间就是最快完成时间
	for(int i=0; i<m; i++)
		if(ans<b[i])
			ans=b[i];
	cout<<ans;
}

三、木桶理论效用最大

木桶理论是指：由多块木板做成的水桶，其装水量取决于最短的那一块木板。

如果木板不可以拼接，那么直接求最小值，就知道木桶的装水情况了
如果木板可以自由拼接呢，那么直接求个平均值也就可以了。
但有一些情况，是较为特殊的，比如下面所说的游戏机电池问题

题目：
小乐有一台使用电池的手持电子游戏机，由于电池的电量不同，所以其使用的时间也就不同。这部机器可以装两块电池，只有一块电池有电是没有办法工作的。如果小乐有两块电池，分别是5、3，那么其使用的最长时间就是3，而5使用完后会剩下2个电，但也没用了，如果小青有3块电池，电量分别是5,3,4，则他可以先让5，3配对使用2小时,再让5、4配对使用3小时,此时电量5的电池已经没电了，而电量3和4的电池分别剩余1个电，让这两个配对，还可以再玩1小时，总共可玩6小时。
输入：
有多组数据，每组数据由两行组成
第一行是一个正整数n，代表有多少块电池
第二行是n个整数，代表电池的使用时间
输出：
每组数据对应一行输出，代表游戏机可玩的最长时间，保留小数点后1位
样例输入：
2
3 5
3
3 3 5
样例输出：
3.0
5.5

分析：

这道题目的重点在于必须要有两节电池，才能使游戏机可用。如果电池可以自由的切分那自然可以用到最后一刻，但电池并不能够自由切分，只可以按一定规则来切分，下面咱们就来研究一下这个切分的规则，

1. 如果2节点池，电量分别是3、5，那么无论如何切分，也只能用3小时。
2. 如果3节电池,电量分别是3、3、5,那么就可以对3、5用2.5小时,而另外一个3、5用2.5小时，最后3、3用0.5小时，加一起是5.5小时。
   
   之所以能够进行划分，是因为剩下的电池总量3+3，是大于最大的电池量5的。如果是这样是这样就可以进行拆分使用，否则就不能拆分。
   按照这个思路，我们统计一下所有电池的总量合计s和最大电池总量maxv
   if(s-maxv<maxv)使用时间就是s-maxv
else使用时间就是s/2.0

code:

#include<iostream>
using namespace std;

int main() {
	int n,a,avg;
	//无限输入
	while(cin>>n) {
		int maxv=0;
		int sumv=0;
		for(int i=1; i<=n; i++) {
			cin>>a;
			sumv+=a;
			if(maxv<a)
				maxv=a;
		}
		//如果去除最大的剩余部分<最大，则剩余部分位最长使用时间
		if(sumv-maxv<maxv)
			printf("%.1lf\n",(sumv-maxv)*1.0);
		else {
			//否则就取平均值
			printf("%.1lf\n",sumv/2.0);
		}
	}
}

四、特殊排队问题

有一些问题，一眼看过去感觉和排队没啥关系，然而实际上是采用排队的思路去解决，只是排队过程中贪心的策略不一样。比如下面的这道找零钱的问题

题目：
小乐所在的乐博机器人学校有一个冰激凌店，学生都非常喜欢光顾,为了避免学生吃坏肚子，每个同学只能够购买一个冰激凌，也不允许帮别的同学代买。每个冰激凌的价格是5块钱，同学们手里没什么大面值的钞票,一般就是5块、10块、20块的面值,
这个小店的老板有一个习惯,每天关门的时候，会把所有的钱都存到银行，这导致他第二天手里没有零钱找给客人,如果客人拿5块钱面值来买自然很好，如果拿10块或20块面值来买东西，就要看他有没有零钱找了，如果没零钱找，他就会让这个客人走，暂时不做他的生意。
这样下来，就会有一些客人买不到冰激凌而离开,而他也少赚了钱,现在请你统计一下,这个小店老板一天究竟能赚多少钱,卖出了多少杯,有多少位客人因为找不找零钱而没有买到。
输入：
第一行一个整数n，代表今天所有到店的客人数
第二行有n个整数，代表今天按照顺序到店人所持钱的面值
输出：
一行，3个整数，分别代表当天的营业额、卖出数量、以及因找零问题放走客人数，中间用空格分开
输入样例：
5
5 10 20 5 5
输出样例：
20 4 1

分析：

这道题一看，怎么也想不到分是一个排队问题,然而实际上却是一个排队问题,排的不是人,而是找零钱的时候,零钱的排队顺序。其实这个问题比较容易理解，因为现实生活中,如果有人拿着20块钱来买个5块的物品,你肯定优先找他一张10块+1张5块，但若你手里没有10块的，也只能找3张5块的了,
所以零钱的排队顺序是:
20的，优先找10+5，否则才找3*5，这就是一种贪心策略。

分析：

#include<iostream>
using namespace std;

int main() {
	int a5=0,a10=0,a20=0,k=0,n,t,m=0;
	//当天的n个客人
	cin>>n;
	for(int i=0; i<n; i++) {
		//当前客人给的面值
		cin>>t;
		//给5元钱不找钱
		if(t==5) {
			a5++;
			k++;
		}
		//给10块找5块
		else if(t==10) {
			if(a5>0) {
				a5--;
				a10++;
				k++;
			} else
				//此客人接待不了
				m++;
		}
		//给20，两种找法
		else if(t==20) {
			//第1种，找1张10块，1张5块
			if(a10>0&&a5>0) {
				a10--;
				a5--;
				a20++;
				k++;
			}

			else if(a5>2) {
				a5-=3;
				a20++;
				k++;
			} else
				//此客人接待不了
				m++;
		}
	}
	cout<<a5*5+a10*10+a20*20<<" "<<k<<" "<<m;
}

除此之外，还有一些类似于渡河之类的问题，也是属于这种特殊排队一类的，遇到这种问题，首先是要识别出这是一个排队问题，在排队的时候，规则是什么，也就是怎么排才能距离自己想要的目标更近。

总结：

1. 对于排一队的问题，要搞清楚如何排才能使所有人的总等待时间最少。
2. 对于排多队，要能够安排好队形，使最快时间内结束掉任务。
3. 对于木桶类问题，要想办法使所有木板尽可能一样长，做到平均，则发挥的效用最大
4. 特殊的排队问题，关键在于识别出是排队问题，然后想是什么排队，以及排队规则是什么。

贪心与背包问题

什么是背包问题：
这个背包是指你有一个背包，里面可以装东西，比如有的体积大、占地多，自然装的数量就少；而有些物品体积小，自然装的就多。而每件物品价值肯定是不同的，体积小的未必价值就小，体积大的未必价值就大。要使得背包装完之后价值最大，这就需要我们规划出一种算法，这种问题我们就称之为：背包问题，随着算法的不断演进，已经不限于使用背包，也可能是运输时候车厢或轮船装载货物，还可能是物品装箱问题。这一类问题统称为背包问题。

我们之后在动态路径规划算法中会进一步学习背包问题

分类：
1. 普通背包：物品是可以分割的，即往包里装的时候空间不够了，只能装下这件物品的一部分，那么我们就把这件物品分成两半，把其中能装进去的一半装进去
2. 0-1背包：物品不可分割，要么装要么不装，总之不能分一半装进去

一、普通背包

在普通背包问题中，物品是可以分割的，如果是这样我们就争取要性价比最高的，那么最终一定得到最大价值。

题目：
阿里巴巴走进了装满宝藏的藏宝洞。藏宝洞里面有N(N <100)堆金币，第i堆金币的总重量和总价值分别是m;, v;(1 < m;,u;≤ 100)。阿里巴巴有一个承重量为T(T <1000)的背包，但并不一定有办法将全部的金币都装进去。他想装走尽可能多价值的金币。所有金币都可以随意分割，分割完的金币重量价值比(也就是单位价格）不变。请问阿里巴巴最多可以拿走多少价值的金币?
输入：
第一行两个整数N,T。
接下来N行，每行两个整数m, v.
输出：
—个实数表示答案，输出两位小数
输入样例：
4 50
10 60
20 100
30 120
15 45
输出样例：
240.00

分析：

有s个种类的物品，知道每个物品的总价值v[i]和总重量n[i]，背包最多装w重量的东西，东西可以分割，让我们求最多价值是多少，我们可以求出每个物品的性价比，比如五块钱两斤的苹果和十块钱三斤的苹果买哪个划算？那肯定是买五块钱两斤的更划算，性价比高的优先装，装完之后转第二个性价比高的，然后一直装到装不下去为止，然后查看所装物品的价值的总和自然就知道结果了。
本题

完整代码：

在这里插入代码片