写在最前面：

此系列中的所有模板全为大佬所写，我只是一个搬运工（？）。

记录：

贪心问题一般分为几种类型，一般的解题思路如下。

1. 把题目化作数学模型。
2. 将问题分成几个小问题。
3. 寻找小问题局部最优解。
4. 把局部最优解合并。 可以看做是一条振荡曲线，选择每一个峰值作为局部最优解。

区间选点&&最大不相交区间数量

第一类问题比如说在几个区间范围内找几个点，使得所有的区间都包含有这个点。求最小值。

第二类问题比如说安排个人的空闲时间做事等这样的问题。 这两类问题可以用一种解题思路来解决：

1. 先把所有的区间按照右端点从小到大排好；
2. 然后选择第一个右端点依次和后面的左端点进行比较，如果大于直接跳过该端点，如果小于则把所求点数+1，并且把下一个作为比较的右端点更新为现在的这个右端点。
3. 最后把统计的结果输出。

下面是模板：

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
const int N=1e6+100;
int n;
struct range
{
    int l,r;
    bool operator <(const range &a)const
    {
        return r<a.r;
    }
}all[N];


int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d %d",&all[i].l,&all[i].r);
    }
    sort(all,all+n);
    int num=0,ed=-2e9;
    for(int i=0;i<n;i++)
    {
        if(all[i].l>ed)
            ed=all[i].r,num++;
    }
    printf("%d\n",num);
    return 0;
}

区间分组

该题目比如说把牛放入畜栏里，有些牛不能放在一起，而且所需要的畜栏最少，求畜栏的数量。

解决过程如下：

1. 先把所有数组按照左端点从小到大排好。
2. 然后选择最后一个左端点依次和前面的左端点进行比较，如果大于直接跳过该端点，如果小于则把所求点数+1，并且把下一个作为比较的右端点更新为现在的这个左端点。

下面是模板：

//待编辑

区间覆盖

该题目详细来说就是选最少的区间把题目所给的区间给覆盖掉。

解决过程如下：

1. 将左端点覆盖。
2. 枚举区间，在覆盖最开始的区间（start）时，选择右端覆盖最大区间，然后将最前端的数据更新（start指向这个区间的右端点）。

下面是模板：

#include <iostream>
#include<cstdio>
#include <algorithm>
#include<climits>
using namespace std;
const int N=1e5;
struct range
{
    int l,r;
    bool operator <(const range &w)const//结构体使用sort的语句
    {
        return l<w.l;
    }
} ra[N];
int main()
{
    int st,ed;
    scanf("%d %d",&st,&ed);
    int n;
    scanf("%d",&n);
    for(int i=0; i<n; i++)
    {
        scanf("%d %d",&ra[i].l,&ra[i].r);
    }
    sort(ra,ra+n);
    int num=0;
    bool flag=false;
    for(int i=0; i<n; i++)
    {
        int j=i,tmp=INT_MIN;//双指针
        while (j<n&&ra[j].l<=st)//看左端点是否包含开始位置
        {
            tmp=max(tmp,ra[j].r);//最大右端点
            j++;
        }
        if(tmp<st)
        {
            num=-1;
            break;
        }
        num++;
        if(tmp>=ed)
        {
            flag=true;
            break;
        }
        st=tmp;//更新开头
        i=j-1;//出循环的判定，所以需要-1

    }
    if(!flag)num=-1;
    printf("%d\n",num);

    return 0;
}

Huffman树（完全二叉树）

题目如 有几堆果子，要合并成一堆，每次消耗的力气是合并两对果子的重量和，求最少花费的力气。

解决过程如下： 最小的点被计算的次数最多（一定深度最深，可以互为兄弟节点），这样就可以局部最优解。 然后合并最小的两个点，剩下了n-1个点（最小的点合并会产生一个新的点），再次排序合并。

下面是模板:

//待编辑