这是关于堆知识的整理 堆是一个二叉树 维护的是一个有序的二叉树
堆中某个结点的值总是不大于或不小于其父结点的值；(大根堆与小根堆)
堆总是一棵完全二叉树。
priority_queue
priority_queue<int, vector
这边的greater其实是一个函数用来比较的！！
堆的stl可以改写
关于改写堆 priority_queue<node, vector<node>,cmp1> s;
struct cmp1{
bool operator()(node x,node y){
return x.h>y.h;//为啥是小根堆？？
}
};
struct node{
int x,y,h;
node(int _x,int _y,int _h)
{
x=_x,y=_y,h=_h;
} // 不会写构造函数
bool operator < (const node &A )
{
return h<A.h;
}
}
这样就改写完成了一个堆
堆其实经常跟贪心结合起来因为堆维护数据的特点一般我们会选择维护一个满足条件：实现最优解的堆故一般和贪心挂钩！！
例子
这道题就是一个标准堆+贪心每次拿出最小的两个合并后又放回去得到的值用ans+起来最终得到答案
堆还有一个极为特殊的结构对顶堆
作用：动态维护第 n 小/大的数
用一个大根堆记录前面的数 用一个小根堆去记录后面的数 前面堆的大小总比后面大1
这样就是一个中位数！！
int x; 大根堆的大小总比小根堆的大小大1！！！
scanf("%d",&x);
if(x>a.top()) b.push(x);
else a.push(x);
int len1=a.size(); //大根堆
int len2=b.size(); //小根堆
if(len1-len2>1)//大根堆更大
{
int z=a.top(); 把大根堆的一个元素拿出来放入小根堆里面
a.pop();
b.push(z);
}else if(len1-len2<1)
{
int z=b.top(); 把小根堆的元素拿出来放入大根堆里面
b.pop();
a.push(z);
}
if(i%2)
printf("%d\n",a.top());
动态维护可变的第 i 小的数 思路特别特别好!!!!
for(i=1;i<=m;i++)
{
while(cnt<geta[i]) //满足geta[i]后有j 个
{
cnt++;
a.push(add[cnt]); //把新的数放进来排个序
b.push(a.top()); //把a中最大的加入b中
a.pop(); //a最大的放入b中只留下j个数
} //这样就动态维护了第j 个数 j也可变!!!
//把a中j个元素输出出去就得到了 前 j 小的数 j还是可变的
//动态维护了一个区间最小值!!!
cout<<b.top()<<'\n';//j++ 了
a.push(b.top());
b.pop();//a中此时能多维护一个数
}
有意思的题目!!!新思路!!!!妙妙妙!!
这道题就挺有意思的说下思路 如果一个个去弄肯定很难那就先读第一个函数的前m个放入堆中然后后面的函数依次加入去比较 跑一个o(nm)的一个遍历即可!!!之后的函数就是一个个去迭代,看到符合条件的就替换掉了,直到不满足就结束进入下一个函数
因为小的不满足比他大的肯定也不满足!!所以结果就已经确定了!!
也有一道有意思的题目!!!
因为是看最