算法文章---贪心

——————————————————贪心——————————————————
贪心算法也叫贪婪算法，就是说在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解。”贪心的本质是选择每一阶段的局部最优，从而达到全局最优。贪心算法没有固定的框架，算法设计的关键是贪婪策略的选择。

贪心的一般情况解题思路可以分为：
1.建立数学模型来描述问题
2.把需要求解得问题分成若干个问题
3.对于每个问题求解，得到子问题的局部最优解
4.把子问题求解，得到局部最优

例子：
我要看许多场演出
可以将一个活动时间长短来排序（错误）
还可以按照活动开始时间选择（错误）
按照活动结束时间选择（正确）
最后一种是正确的，也就是最贪心的一种
用代码实现：
#include <bits/stdc++.h>
using namespace std;struct node{
        int x,y;
}f[1000005];
int n,ans,t;bool cmp(node a,node b) {
        return a.y<b.y;
}
int main(){       
        cin>>n;
        for(int i=1;i<=n;i++){       
                cin>>f[i].x>>f[i].y;       
        }       
        sort(f+1,f+n+1,cmp);//按照活动结束时间从早到晚排序
        t=f[1].y,ans=1; //第一场活动一定能参加       
        for(int i=2;i<=n;i++){//后面的每一场比较 能参加都参加
                if(f[i].x>=t){//当前活动开始时间晚于上一场活动的结束时间                                                ans++; //活动数目加一                       
                        t=f[i].y;//更新结束时间               
                }       
        }       
        cout<<ans;       
return 0;
}