1. 区间选点

步骤 : 
1.将区间按右端点排序
2.遍历区间,如果该区间中不包含最后选的那个点,则选取区间右端点
如果包含最后选的那个点,则跳过
3.输出所选点的个数

#include<iostream>
#include<algorithm>
using namespace std;
const int N=100010;
struct Range
{
    int l,r;
}range[N];
//定义了N个Range结构体,每个结构体包含l和r(左右端点)两个参数
    bool cmp(Range a,Range b) 
    /*
    sort函数在cmp函数的返回值为真时,将其第一个元素放在前面
    这里就是把右端点小的区间放在前面
    */
    {
    return a.r<b.r;
    }
int main()
{
    int n;
    scanf("%d",&n);
    for (int i=0;i<n;i++)
    {
        scanf("%d%d",&range[i].l,&range[i].r);
        //输入每个Range的左右端点
    }
    sort(range,range+n,cmp);
    int res=0,ed=-2e9;
    //res : 当前点的数量   ed : 上一个区间的右端点
    for (int i=0;i<n;i++)
    {
        if (range[i].l>ed)
        //如果两个区间不相交,重置右端点
        {
            res++;
            ed=range[i].r;
        }
    }
    printf("%d\n",res);
    return 0;
}

2. 区间分组

步骤 : 
1.将区间按左端点排序
2.遍历区间,记录每个集合中保存的区间的最右侧端点
如果当前区间的左端点小于右侧端点最小的那个集合
则把该区间放到该集合
否则新开一个集合,把当前区间放到新开的集合中
3.输出集合的个数

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int N=100010;
struct Range
{
    int l,r;
}range[N];
    bool cmp(Range a,Range b) 
    {
    return a.l<b.l;   //将区间按左端点排序
    }
int main()
{
    int n;
    scanf("%d",&n);
    for (int i=0;i<n;i++)
    {
        scanf("%d%d",&range[i].l,&range[i].r);
    }
    sort(range,range+n,cmp);
    priority_queue<int,vector<int>,greater<int>> heap;
    //从小到大排序的优先队列,保存所有集合的右端点
    for (int i=0;i<n;i++)   //遍历区间
    {
        Range a=range[i];
        if (heap.empty()||heap.top()>=a.l) heap.push(a.r);
        /*
        如果队列为空或者堆顶的右端点小于当前区间的左端点
        则新开一个集合
        else
        {
            heap.pop();
            heap.push(a.r);
            //否则更新堆顶的右端点
        }
    }
    printf("%d\n",heap.size());
    //堆里有几个元素,说明就有几个集合
    return 0;
}

3. 区间覆盖

步骤 : 
1.将区间按左端点排序
2.遍历区间，在所有包含start的区间中,选择右端点最大的区间
然后将start更新成右端点的值

#include<iostream>
#include<algorithm>
#include <queue>
using namespace std;
const int N=100010;
struct Range
{
    int l,r;
}range[N];
    bool cmp(Range a,Range b) 
    {
    return a.l<b.l;   //将区间按左端点排序
    }
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",&range[i].l,&range[i].r);
    }
    sort(range,range+n,cmp);
    int res=0;   //res : 当前区间的数量
    bool success=false;   //判断是否成功,初始值为失败
    for (int i=0;i<n;i++)
    {
        int j=i,r=-2e9;
        while (j<n&&range[j].l<=st)
        {
            r=max(r,range[j].r);
            j++;
        }
        //在所有包含start的区间中,选择右端点最大的区间
        if (r<st)   
        //当前右端点的最大值小于st,则一定无法覆盖区间
        {
            res=-1;
            break;
        }
        res++;   //区间数量+1
        if (r>=ed)   
        //当前右端点的最大值大于ed,则说明能够覆盖区间
        {
            success=true;
            break;
        }
        st=r;   //将start更新成目前右端点的最大值
        i=j-1;
        //筛掉右端点在start之前的区间,因为有i++,所以这里是j-1
    }
    if (!success) res=-1;
    printf("%d\n",res);
}

4. Huffman树

步骤 : 选择最小的两个堆进行合并
原理 : 前面合并的果子重量,后面的每一步都要再合并一次
所以先合并重量小的,消耗的体力最小

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
int main()
{
    int n;
    scanf("%d",&n);
    priority_queue<int,vector<int>,greater<int>> heap;
    //从小到大排序的优先队列,保存所有果子重量的大小
    while (n--)
    {
        int x;
        scanf("%d",&x);
        heap.push(x);
    }
    int res=0;   //当前消耗体力的数量
    while (heap.size()>1)   //如果还有两个堆没有合并
    {
        int a=heap.top();heap.pop();
        int b=heap.top();heap.pop();
        res+=a+b;
        heap.push(a+b);   //合并两个堆
    }
    printf("%d\n",res);
    return 0;
}

5. 绝对值不等式

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int q[N];
int main()
{
    int n;
    cin>>n;
    for (int i=0;i<n;i++) cin>>q[i];
    sort(q,q+n);   //从小到大排序
    int res=0;
    for (int i=0;i<n;i++) res+=abs(q[i]-q[n/2]);
    //货仓位置取数轴中点时,到每家商店的距离最短
    cout<<res;
    return 0;
}

6. 贪心用到的数学公式

未完待续