Ocrosoft
内容导引：
贪心算法的基本思想
贪心算法的基本思路
贪心算法的进行过程
基本题型与例题解析
基本思想：
基本要素：
基本思路：
从问题的初始状态开始，往最终状态前进，每次都选择当前最好的选择。当到达最终状态时停止；如果不能再作出选择，又未到达最终状态，那么这个问题不能或利用贪心思想不能到达最终状态，停止。
执行过程：
用一个背包问题来解释：
有一个背包，其容量M一定。物品有若干个，要求尽可能让装入背包中的物品的总价值最大，但是不能超过总容量。
那么贪心思路有一下三个：
思路分析：
如何解决背包问题：
种类一：一般贪心(交换)问题
HDU 1009 Fat Mouse’ Trade
Fat Mouse 准备了M磅猫粮，准备和看守存放了他最喜欢的食物-咖啡豆的房间的猫进行交易。猫看守着N间房间，第i间房间存放了J[i]磅咖啡豆，交换所有咖啡豆需要F[i]磅的猫粮，FM不必交换整个房间的咖啡豆，也就是说，他可以用(F[i]*a)%磅的猫粮交换得到(J[i]*a)%磅咖啡豆。现在他请你帮忙，帮他交换到最多数量的咖啡豆。
数据分析如下：
分析：
题目描述似乎和之前的背包问题很相像，但是题目多了一个可以用一部分猫粮换取一部分咖啡豆的条件。如果那个背包问题也加入这样的条件，那就可以保证背包能够装满，这样就可以用贪心去解决。
那么这个问题，可以选择之前的思路三，选择放前单位猫粮换取的咖啡豆最多的房间进行交易，直到猫粮用完。
得出解决方案后，先验证一下第一组数据，三个房间分别是 3.5；1.333；2.5，先换房间1和3的，都可以全部换到。剩下房间2不能换到所有的咖啡豆，因为猫粮剩余1，只能换到1/3，那么结果就是7+5+4*(1/3)=13.333，答案正确。
题解传送门：http://www.ocrosoft.com/?p=200
类型二：时间安排问题(区间覆盖)
HDU 2037 今年暑假不AC
小A列出了一些想看的电视节目，上面表明了电视节目的开始和结束时间，但是一些电视节目是冲突的，现在他想尽可能多地而且完整地看电视节目，请你帮忙。
数据分析如下：
分析：
时间安排问题，用贪心总能得到整体最优解，用数学归纳法可以证明，证明不重要，从略。
可以先对所有的节目以结束时间从早到晚进行排序，结束时间相同的时候，按照开始时间从早到晚排序。
然后看第一个节目，它的开始时间最早，结束时间最早，那么这个节目是一定要看的。然后后面的节目都对比前一个看的节目的结束时间，如果此时还在看上一个节目，那么继续看前一个节目，放弃这一个节目。直到分析完所有节目。
题解传送门：http://www.ocrosoft.com/?p=204
类型三：线段覆盖问题(区间覆盖)
这种类型和类型二非常类似，要求计算一些线段覆盖的总长度，只需要对类型二稍加修改，排序的时候先按照开始时间排序，再按结束时间排序。总长先记为线段1的全长，然后线段2和线段1比较，如果线段2不与线段1重复，总长就加上线段2的全长；如果线段2结束点在线段1结束点前，那么线段2长度不计；如果线段2与1重复且结束点不在线段1内部，则总长加上线段1结束点到线段2结束点的长度。
如下数据：答案为13。
#include <set>
#include <map>
#include <list>
#include <cmath>
#include <stack>
#include <queue>
#include <ctime>
#include <string>
#include <cstdio>
#include <vector>
#include <cctype>
#include <climits>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define ms(a) memset(a,0,sizeof(a))
#define INF INT_MAX
#define MAXN 500+10
using namespace std;
struct Node
{
int s,f;
bool operator<(const Node t)const
{
if(s==t.s)return f<t.f;
else return s<t.s;
}
} node[15];
int n;
int main()
{
while(cin>>n&&n)
{
for(int i=0; i<n; i++)
scanf("%d%d",&node[i].s,&node[i].f);
int ans=node[0].f-node[0].s;
for(int i=1,j=0;i<n;i++)
{
if(node[i].s>node[j].f)//如果这条线段跟前面的没有重叠
{
ans+=node[i].f-node[i].s;//计算这条线段的全场
j=i;
}
else
{
if(node[i].f<=node[j].f)continue;//如果这条线段结束点在上一条线段的内部，这条线段不计长度。
//可能会考虑如果这条线段开始比上一条长的情况，但是排序的时候已经排除了这种情况。
ans+=node[i].f-node[j].f;
j=i;
}
}
printf("%d\n",ans);
}
return 0;
}
类型四：数字组合问题
分析：
不能拆分的情况，有两种，1是只有一位，2是去掉0后只有一位，在判断的时候这两种可以归为一种。例：1和10000。
能拆分的情况，一定是拆分成n-1位和1位的两个数，这个1位的数，一定取除了0以外的最小的数。n-1位的数就像例1一样，从大到小排好。题目要求输出和，进行一下大数加法就可以了。
贪心算法到这里就结束了，如果有错误请指正，谢谢。