[数据结构与算法]贪心算法（Greedy Algorithm）

贪心算法：

在对问题求解时，总是作出在当前看来是最好的选择。

也就是说，不从整体上加以考虑，所作出的仅仅是在某种意义上的局部最优解（是否是全局最优，需要证明）。

题目链接：Problem - 1050 (hdu.edu.cn)

解题代码

#include<iostream>
using namespace std;

int main()
{
	int t,i,j,N,P[200];
	int s,d,temp,k,MAX;
	cin>>t;
	for(i=0;i<t;i++)
	{
		for(j=0;j<200;j++)
			P[j]=0;
		cin>>N;
		for(j=0;j<N;j++)
		{
			cin>>s>>d;
			s=(s-1)/2;
			d=(d-1)/2;
			if(s>d)
			{
				temp=s;
				s=d;
				d=temp;	
			}
			for(k=s;k<=d;k++)
				P[k]++;
		}
		MAX=-1;
		for(j=0;j<200;j++)
		{
			if(P[j]>MAX)
				MAX=P[j];
		}
		cout<<MAX*10<<endl;
	}
	return 0;
}

运行结果

---------------------------------------------------我是分割线---------------------------------------------------------------

拓展：可图性判定

两个概念：

1.度序列：若把图G所有顶点的度数排成一个序列S，则称S为图G的度序列。

2.序列是可图的：一个非负整数组成的有限序列如果是某个无向图的度序列，则称该序列是可图的。

·Havel-Hakimi 定理

由非负整数组成的非增序列S：d1,d2,...,dn(n ≥ 2，d1 ≥ 1）是可图的，当且仅当序列S1：d2-1,d3-1,...,dd1-1,dd1+2,...,dn 是可图的。

其中，序列 S1 中有 n-1 个非负整数，S序列中d1后的前d1个度数（即d2~d1+1)减1后构成S1中的前d1个数。

特别说明：

若要用贪心算法求解某问题的整体最优解，必须首先证明贪心思想在该问题的应用结果就是最优解！！