贪心

贪心算法是指在对问题求解时，总是做出在当前看来是最优的决策换言之，就是不从全局最优方面考虑，只考虑局部最优情况贪心算法有时可以得到全局的最优解，这取决于贪心的策略

1.排队接水问题：有N个小朋友来接水，每个人接水要用ai的时间，求最小的等待总时间。等待总时间是指所有小朋友的等待时间之和显然这是一个小学奥数中的简单题.. 我们让接水时间短的人排在前面，时间长的人排在后面，可以证明这种方案是正确的

#include<iostream> 
#include<cstdio>
#include<algorithm>
#include<iomanip>
using namespace std;
struct people{
	int t;
	int x;
}a[1001];
bool cmp(people t1,people t2)
{
	return t1.t<t2.t;
}
int main()
{
	int n;
	double sum=0;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i].t;
		a[i].x=i;
	}
	sort(a+1,a+n+1,cmp);
	for(int j=1;j<=n;j++)
	{
		cout<<a[j].x<<" ";
		if(n-j>=1)sum+=a[j].t*(n-j);
	}
	cout<<endl;
	printf("%.2lf",sum/n);
	return 0;
 }

不是所有的情况都可以贪心一般来说，当我们试图用贪心做法来解决一道题的时候，最好能先证明贪心的正确性，否则只靠猜测一般来说是不正确的

一个错误贪心的例子

有N个小朋友，M块糖，给出一个二维数组，其中aij代表第i个小朋友获得j块糖之后的喜悦值要求求出所有小朋友的喜悦值之和最大是多少可以想到一种贪心方式是：对于每块糖，我们选择获得这块糖之后对答案贡献最大的小朋友，把糖分给它

反例：2 3 1 100

2.最大排列

有一个长度为N的序列，每个元素互不相同现在给你K次操作机会(可以不用完)，每次可以交换相邻两个数求在这种条件下，你能交换出的字典序最大的序列是什么 N<=5000

可贪心：由于要求字典序最大，也就是说我们的目标是：让第一个数尽可能大，在这个基础上让第二个数尽可能大… 所以每次我们在可选的范围内找到一个最大的数，把他交换到前面，然后处理下一位即可。

3.运输

黑板上N个正整数给出一个正整数K 每次你可以擦掉黑板上的两个数A,B 然后在黑板上写下(A+B)/K向下取整的值直到只剩下一个数问剩下的数最少是多少 N<=10000

可贪心：

错误的贪心策略：从大到小依次擦掉可以举出反例，也可以证明每步的策略不同所以我们在考场上应该多出几组数据来尝试卡掉自己的贪心策略正确的贪心策略：每次选取最大的两个数擦掉。

4.NOIP 1999防御导弹

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够达到任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。已知敌国每颗导弹的高度

问：用一套系统最多能拦截多少导弹？

如果要拦截所有导弹最少要配备多少套这种导弹拦截系统？

第一问贪心不可做

第二问贪心可做：、#include<iostream>#include<cstdio>#include<iostream>

#include<algorithm>
#include<cstring>
using namespace std;
int main()
{
	int a[1001]={0},k=0,i=0,xi[1001]={0},ans=0;
	while(cin>>a[i++]);
	i--;
	for(int ii=0;ii<i;ii++)
	{
		int p=0;
		for(int j=1;j<=ans;j++)
		{
			if(xi[j]>=a[ii]) 
			{
				if(p==0) p=j;
				if(xi[p]>xi[j]) p=j; 
			}
		}
			if(p==0) 
			{
				ans++;
				xi[ans]=a[ii];
			}
			else
			{
				xi[p]=a[ii]; 
			}
	} 
	cout<<ans<<endl; 
    return 0;
}
5.Cow Acrobats

有N头牛，每头牛有体重和力量两个属性，他们要在一起叠罗汉每头牛的危险值=它上面所有牛的体重之和-这头牛的力量求所有牛的最大危险值最小是多少？

可贪心：

贪心策略：把所有牛按照体重+力量从小到大排序，小的在上面正确性证明：对于一种排列方案，如果我们可以找到相邻的两头牛i,j(i在上)使得交换它们的位置之后答案变小，则这种方案一定不是最优解我们考虑不想出现这种情况需要满足什么，设体重为a，力量为b，上面所有牛的体重之和为W，则有： max(W-bi,W+ai-bj)<=max(W-bj,W+aj-bi) 化简之后得ai+bi<=aj+bj 也就是说，若不按照ai+bi从小到大进行排列则一定不是最优解而按照ai+bi从小到大排列只有一种方案(相同的是等价的)，所以这就是最优解。

编码问题与哈夫曼树

在数据通信中，我们常需要把信息进行编码，一般我们会编成二进制码当我们收到一串二进制码进行解码时，必须要使解得的信息唯一这就需要编码时任意一个二进制串都不是另一个二进制串的前缀而每个信息使用的频率不同，如英文单词中字母a远比c的使用频率高这就出现了一个问题，如何设计编码方案，使得信息的期望长度最短，即pi*li的和最小，也就是编码问题

每次找2个pi最小的元素合并并删除，并把他们的pi相加后重新加进来这个过程可以使用堆来维护最后会形成一颗二叉树，就叫哈夫曼树

K叉哈夫曼树

每次找k个pi最小的合并即可