前缀和
b站：https://www.bilibili.com/video/BV1wA411v7F3?from=search&seid=12091630423975717527 https://www.bilibili.com/video/BV1aE411b7Eh?from=search&seid=12091630423975717527
题目：ACWING的 以及CCF20201202
优先队列
贴了一堆图片 讲一下优先队列 来自大佬：https://blog.csdn.net/c20182030/article/details/70757660和 https://www.bilibili.com/video/BV1PK411j7fj?from=search&seid=10378005199525922726 网太差了让我的心情很不好
优先队列是一种特殊的队列，在学习堆排序的时候就有所了解。功能强大在哪里呢？ 四个字：自动排序。
一个优先队列声明的基本格式是：priority_queue<结构类型> 队列名;
//基本的数据类型
priority_queue <int> i;
priority_queue <double> d;
//是结构体
priority_queue <node> q; //要求该结构体里重载‘<’小于符号
// 排序
priority_queue <int,vector<int>,greater<int> > q;
priority_queue <int,vector<int>,less<int> >q; //后面> >分开写 连在一起不是右移符号了嘛【less这种写不写的，效果和默认一样，大根堆】
怎么说呢，就是优先队列是自动排序的，默认大根堆，就是降序，由大到小输出
priority_queue <int> q;
int main()
{
q.push(10),q.push(8),q.push(12),q.push(14),q.push(6);
while(!q.empty())
printf("%d ",q.top()),q.pop();
//14 12 10 8 6
}
你要是想变成由小到大升序输出，需要做出改变：
基本数据类型：priority_queue <int,vector
结构体：需要在结构体的声明里，对优先队列的小于符号做重载
//记住就行 就是这么敲 都是这个套路
附带上优先队列priority_queue的常用函数
q.size();//返回q里元素个数
q.empty();//返回q是否为空，空则返回1，否则返回0
q.push(k);//在q的末尾插入k
q.pop();//删掉q的第一个元素
q.top();//返回q的第一个元素 [取得堆顶 所以top]
附带上几个例题
CCF20170902 钥匙盒
BZOJ 1724
#include<bits/stdc++.h>
using namespace std;
priority_queue<int,vector<int>,greater<int> >q;//一个按从小到大排序的优先队列
int main(){
scanf("%d",&n);//快速输入 当数据量比较大的时候
for(int i=1;i<n;i++){
scanf("%d",&a[i]);//
q.push(a[i]);
}
for(int i=1;i<n;i++){
int x=q.top();q.pop();
int y=q.top();q.pop();
ans+=x+y;
q.push(x+y);
}
printf("%d",ans);
return 0;
}
//这个题用到了优先队列+贪心+逆向思维
//例子3块木板长度=8+5+8=21 按8+5/8划第一刀:收费13+8=21 8/5划第二刀收8+5 总共=21+13=34
//如果按8+8+5即：first=16+5=21 second：8+8=16 21+16=37
//所以说白了已经给了你划分好的木板的长度了 要往回推
//想到哈夫曼树了嘛 就是这个 需要把最小的两个数合并 【==》先把数据中最小的两个数相加，这两个数从数据中刨除去，二者之和再加入数据中
POJ3197：
https://www.cnblogs.com/hrj1/p/11211690.html
#include<bits/stdc++.h>
using namespace std;
const int maxn=;
//c++输入大数据必备：https://blog.csdn.net/hualian_/article/details/95329939
int read(){
int s=0,f=1;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
s=(s<<3)+(s<<1)+(c^48);
c=getchar();
}
return s*f;
} //！！！！！！！
struct cow{
int start,over;
friend bool operator < (cow a,cow b){//！！！！！！！运算符重载函数
return a.over>b.over;
}//变成升序了
//优先队列默认由大到小 所以如果想由小到大就是这个模板照抄
};
priority_queue<cow> q;
bool cmp(cow a,cow b){//sort函数排序默认由小到大 想改变的话【除int外其他形式/降序】就是加个cmp函数就行
return a.start<b.start;
}
int main(){
n=read();
for(int i=1;i<=n;i++){
c[i].start=read();
c[i].over=read();
}
sort(c+1.c+1+n,cmp);
int ans=1;//肯定要占一间
q.push(c[1]);
for(int i=2;i<=n;i++){
cow x = q.top();
if(c[i].start>x.over){//腾出来位置了
q.pop();
q.push(c[i]);
}else{
ans++;
q.push(c[i]);
}
}//q是一个按产奶开始到结束时间由小到大排列的优先队列 所以只要位于队首的奶牛还没产完就得再开一个棚子
cout<<ans;
return 0;
}
//这题跟CCF的有点相像，牛的使用时间已经给出来了，所以需要先按照牛开始使用的时间由小到大进行排序
//无论几头牛 肯定要占用一个棚子嘛 所以直接把按时间排列的第一头产奶牛到第一个棚子
//其他的进入循环就好
关于sort的这个cmp：
JZOJ,Luogu P5119：
https://www.luogu.com.cn/problem/P5120
看视频学到的一些知识：堆(大/小)增加删除一个元素的时间是O(logN),找到最大最小值O(1)/顶端嘛 看视频前面吧我也说不清