贪心 \(\sf\small\color{gray}Greedy\)

基本思想

贪心，从字面上去理解：
一个人，非常贪心，他不管做出这一步决定后会发生什么，他只管眼前的利益。
这就是贪心。
当然，这个算法的劣处也显现出来：

他不管做出这一步决定后会发生什么。

也就是说，如果这一步片面上是最优的，但会影响到后面酿成严重后果，我们就不能用贪心。
我们把这样的事例称作有 \(\sf\color{red}后效性\) 。
显然，贪心适用于没有后效性的最值问题。
每一次贪下最优的片面抉择，最后，便可算出全局最优。

线段覆盖

现在有 \(\sf n\) 个数轴正半轴上的线段，每个线段的端点是知道的。
这些线段互不能重叠，最多能有多少条线段同时存在？

如果有两条线段 \(\sf(a_1,b_1)\) 和 \(\sf(a_2,b_2)\)，那条线段对后面线段放置的影响最小呢？
答案是 \(\sf b\) 小的那个。
因为右边靠左，就留出了更多的空间给后面的线段了。
所以我们只需要给线段们按右端点排序，然后来检查能放几个就好啦。

#include<cstdio>
#include<algorithm>
struct Line
{
	int Start,End;
	bool operator<(Line m)const{return End<m.End;}
}Lines[1000100];
int N;
int main()
{
	scanf("%d",&N);
	for(int i=0;i<N;i++)
		scanf("%d %d",&Lines[i].Start,&Lines[i].End);
	std::sort(Lines,Lines+N);
	int Now=0,Ans=0;
	for(int i=0;i<N;i++)
		if(Now<=Lines[i].Start)
			Ans++,Now=Lines[i].End;
	printf("%d",Ans);
	return 0;
}

合并果子

在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。
每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过 \(\sf n-1\) 次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。
假定每个果子重量都为1，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。

板中板子题。
贪心策略应该很好想：
每次合并最小的两堆，花费的力气就是最小的了。
其实问题在模拟上。
我们可以使用一个小根堆来维护我们的果子堆。

priority_queue< int,vector<int>,greater<int> > a;

每次取出堆顶最小的两个，合并之后在把他装回堆，直到只剩下一堆果子。

#include<cstdio>
#include<queue>
using std::priority_queue;
priority_queue< int,std::vector<int>,std::greater<int> > a;
int N,Ans,o;
int main()
{
	scanf("%d",&N);
	for(int i=0;i<N;i++)
		scanf("%d",&o),
		a.push(o);
	while(a.size()!=1)
	{
		const int o1=a.top();a.pop();
		const int o2=a.top();a.pop();
		a.push(o1+o2);
		Ans+=o1+o2;
	}
	printf("%d",Ans);
	return 0;
}

算法优劣

其实我在开头就说过了：

他不管做出这一步决定后会发生什么。

也就是说，如果这一步片面上是最优的，但会影响到后面酿成严重后果，我们就不能用贪心。
我们把这样的事例称作有 \(\sf\color{red}后效性\) 。 显然，贪心适用于没有后效性的最值问题。
每一次贪下最优的片面抉择，最后，便可算出全局最优。

他不适用于算带后效性的情况，这一点缺，还得请动态规划来填。
还有，大家也看到了，贪心其实和递推一样，码量不大，难的是思维。
所以在用贪心之前，你需要证明，此题贪心无后效性，不然……

完结散花
凑个编辑页面的100行