科技网站有哪些,海南省建设网站的公司,百度站长工具怎么查排名,怎么做一个网站出来我发现之前一版在电脑上看 常用函数部分 没有问题,由于是手打上去的,在手机上看会发生错位问题,现已将电脑原版 常用函数部分 截图改为图片形式,不会再发生错位问题,非常感谢大家的支持 ### priority_queue优先队列出现频率非常高,尤为重要(是一定要掌握的数据结构)
1.queue队… 我发现之前一版在电脑上看 常用函数部分 没有问题,由于是手打上去的,在手机上看会发生错位问题,现已将电脑原版 常用函数部分 截图改为图片形式,不会再发生错位问题,非常感谢大家的支持 ### priority_queue优先队列出现频率非常高,尤为重要(是一定要掌握的数据结构)
1.queue队列
queue是一种先进先出(FIFO)的数据结构queue提供了一组函数来操作和访问元素,但它的功能相对较简单
queue的定义和结构如下:
template class T, class Container dequeT
class queue;
T:表示存储在queue中的元素的类型。Container:表示底层容器的类型,默认为deque,也可以使用其他容器类型,如listqueue的内部实现使用了底层容器来存储元素,并且只能通过特定的函数来访问和操作元素
以下是一些queue的常用函数: ### 这就像一个队伍———————————————————————
pop出去 —— 1 2 3 4 5 6 —— push进来——————————————————————— 2.priority_queue优先序列
priority_queue与普通的队列不同,priority_queue中的元素是按照一定的优先级进行排序的默认情况下,priority_queue按照元素的值的从大到小进行排序,即最大元素位于队列的前面
priority_queue的定义和结构如下:
template class T,ContainervectorT,class Comparelesstypename Container::value_type
class priority_queue;
T:表示存储在priority queue中的元素的类型Container:表示底层容器的类型,默认为vector,也可以使用其他容器类型,如dequeCompare:表示元素之间的比较函数对象的类型,默认为less即按照元素的值进行比较priority_queue的内部实现使用了底层容器来存储元素,并且只能通过特定的函数来访问和操作元素
以下是一些priority_queue的常用函数 ### 介绍几种优先队列修改比较函数的方法
1.第一种
#includebits/stdc.h
struct Compare{ //仿函数bool operator()(int a,int b){ //()重载 //自定义比较函数return ab; //小根堆 }
};
int main(){std::priority_queueint,std::vectorint,Compare pq;return 0;
}
默认的是大根堆
2. 第二种
#includebits/stdc.h
auto compare[](int a,int b){//自定义比较函数,按照逆序排列return ab;
};
int main(){std::priority_queueint,std::vectorint,decltype(compare)pq(compare);return 0;
} ### 如果优先队列中的元素类型比较简单,可以直接使用greaterT来修改比较方法 priority_queueint,vectorint,greaterrint pq;
//std::greater函数对象定义在functional头文件中 3.deque双端队列 deque(双端队列)是一种容器,它允许在两端进行高效的插入和删除操作deque是由一系列连续的存储块(缓冲区)组成的,每个存储块都存储了多个元素这使得deque能够在两端进行快速的插入和删除操作,而不需要移动其他元素
deque的定义和结构如下:
template class T,class AllocatorallocatorT
class deque;
T:表示存储在deaue中的元素的类型Allocator:表示用于分配内存的分配器类型,默认为allocator,deque的内部实现使用了一系列的存储块(缓冲区),每个存储块存储了多个元素,并且通过指针进行连接这种设计使得在两端进行插入和删除操作的时间复杂度为常数时间,即0(1)
### “单调队列”将使用双端队列来实现(单纯考察双端队列的并不常见)
以下是一些deque的函数 ### 10~12个并不常见 4.例题讲解:
题号:lanqiao OJ 1113
1.CLZ银行问题 #includebits/stdc.h
using namespace std;
int main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int m;cinm;queuestring V,N;while(m--){string op;cinop;//判断是否为来到窗口//IN情况,推入nameif(opIN) {string name,q;cinnameq;if(qV){V.push(name);}else{N.push(name);} }//out情况,弹出nameelse{string q;cinq;if(qV){V.pop();}else{N.pop();}} }//输出VIP窗口namewhile(V.size()){coutV.front()\n; V.pop();} //输出普通窗口namewhile(N.size()){coutN.front()\n; N.pop();} return 0;
} 每次都会弹出,队列虽然是一种线性结构但它是不能遍历的 题号:lanqiao OJ 741
2.合并果子 ### 这里用到一点点贪心1.先将1和2合并就消耗了3点体力,再将3和9合并就消耗了12点体力,共消耗15点体力2.先将2和9合并就消耗了11点体力,再将1和11合并就消耗了12点体力,共消耗23点体力方案1更省体力那么思路就是每次找到一大堆数字中拿出来最小的两个求和,再放回去(使用优先队列)### 这道题注意要开long long(int大概是2e9可能会超范围)
#includebits/stdc.h
using namespace std;
using lllong long;
int main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int n;cinn; //这里直接用队列就好了,没必要再存数组里 priority_queuell,vectorll,greaterll pq; //类型比较简单,默认是大根堆,要的是小根堆把less直接改成greaterfor(int i1;in;i){ll x;cinx;pq.push(x);} ll ans0;while(pq.size()2){//这里pop出来两个最小的数,也就是小根堆顶部的两个数 ll xpq.top();pq.pop();ll ypq.top();pq.pop();ansxy; //求和pq.push(xy); //把最小数的和push回去 } coutans\n; return 0;
}
