stl相关知识

#include<queue>
priority_queue<Type, Container, Functional>

Type为数据类型， Container为保存数据的容器，Functional为元素比较方式。

如果不写后两个参数，那么容器默认用的是vector，比较方式默认用operator<，也就是优先队列是大顶堆.

建立小顶堆的方法
priority_queue<int, vector<int>, greater<int> > heap;
可实现的操作

和队列基本操作相同:
top 访问队头元素
empty 队列是否为空
size 返回队列内元素个数
push 插入元素到队尾 (并排序)
emplace 原地构造一个元素并插入队列
pop 弹出队头元素
swap 交换内容

pair相关知识

1.pair是将2个数据组合成一组数据，当需要这样的需求时就可以使用pair。如stl中的map就是将key和value放在一起来保存。
2.当一个函数需要返回2个数据的时候，可以选择pair。 pair的实现是一个结构体，主要的两个成员变量是first second

pair<T1, T2> p1;            //创建一个空的pair对象（使用默认构造），它的两个元素分别是T1和T2类型，采用值初始化。
pair<T1, T2> p1(v1, v2);    //创建一个pair对象，它的两个元素分别是T1和T2类型，其中first成员初始化为v1，second成员初始化为v2。
make_pair(v1, v2);          // 以v1和v2的值创建一个新的pair对象，其元素类型分别是v1和v2的类型。
p1 < p2;                    // 两个pair对象间的小于运算，其定义遵循字典次序：如 p1.first < p2.first 或者 !(p2.first < p1.first) && (p1.second < p2.second) 则返回true。
p1 == p2；                  // 如果两个对象的first和second依次相等，则这两个对象相等；该运算使用元素的==操作符。
p1.first;                   // 返回对象p1中名为first的公有数据成员
p1.second;                 // 返回对象p1中名为second的公有数据成员
typedef pair<p1,p2> PII;

贪心问题

当前决策对后一次决策影响尽量小,并且处理操作可以适用于每一次操作

区间贪心问题

注意排序之后如果要按原来输入顺序输出的话,需要加入一个序号标签

区间线段不重复问题(112. 雷达设备)

策略:每次选择都给后面的选择留更多的几会
将给出的区间按照右端点排序
当不重叠的时候计数器++表示可选取该段(重叠的区间有相同的效益)

#include<iostream>
#include<algorithm>
typedef pair<int,int> PII;
using namespace std;
PII a[1010];
int main()
{
    sort(a,a+n);
    last=a[0].second;
    int cnt=1;
    for(int i=1;i<n;i++)
    {
        if(a[i].first>last)
        {
            last=a[i].second;
            cnt++;
        }
    }
    cout<<cnt<<endl;
}

区间合并的最小组数(111. 畜栏预定)

策略:按照左端点从小到大排序,新加入的区间是否可以加入目前结束时间最晚的,可以的话就直接加入是局部最优解,可以放到其他组但是并不是最优
所以每次需要判断是否大于最小值,如果大于则与最小值合并更新最小值,如果小于就直接再开一个组,所以需要用到优先级队列,最后优先级堆列的size就是组数

#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
typedef pair<int,int > PII;
int n;
PII a[1010];
int main()
{
    priority_queue<PII,vector<PII>,greater<PII>> heap;
    heap.push(a[0]);
    sort(a,a+n);
    PII group;
    for(int i=1;i<n;i++)
    {
        if(heap.top().second<a[i].first)
        {
            PII c=heap.top();
            heap.pop();
            group={a[i].second,c.first};
            heap.push(group);
        }else{
            group={a[i].second,heap.size()+1};
            heap.push(group);
        }
    }
    cout<<heap.size()<<endl;
}

区间选点问题(110防晒霜)

策略：将区间右端点从小到大排序,每次尽量选择每个区间最后的点
(具体其实看题目,防晒霜就是尽量选择前面的点避免重复,因为要避免有重叠部分用同一瓶防晒)

代码跟区间重复问题一样