案例学习网站建设方案,谷歌关键词排名查询工具,精品个人网站源码下载,微信群 网站建设目录
queue队列
常用的deque函数
priority_queue队列#xff08;非常重要#xff09;
priority_queue常用函数
优先队列修改比较函数的方法
1.仿函数方法
2.自定义比较函数
deque双端队列
常用的函数
例题1
题目描述
输入描述
输出描述
示例输入输出
解
例题…目录
queue队列
常用的deque函数
priority_queue队列非常重要
priority_queue常用函数
优先队列修改比较函数的方法
1.仿函数方法
2.自定义比较函数
deque双端队列
常用的函数
例题1
题目描述
输入描述
输出描述
示例输入输出
解
例题2
题目描述
输入描述
输出描述
输入输出示例
输入
输出
解 queue队列
queue是一种先进先出(FIFO)的数据结构。
queue提供了一组函数来操作和访问元素但它的功能相对较简单。
queue的定义和结构如下:
templateclass T,class Container dequeT
class queue;
T:表示存储在queue中的元素类型。
Container表示底层容器的类型默认为queue。也可以使用其他容器类型如list。
queue内部实现使用了底层容器来存储元素并且只能通过特定的函数来访问和操作元素。
常用的deque函数
函数 描述 时间复杂度
push(x) 在队尾插入元素x O(1)
pop() 弹出队尾元素 O(1)
front() 返回队首元素 O(1)
back() 返回队尾元素 O(1)
empty() 检查队列是否为空 O(1)
size() 返回队列中元素的个数 O(1)
priority_queue队列非常重要
priority_queue与普通队列不同priority_queue中的元素是按照一定的优先级进行排序的。默认情况下priority_queue按照元素的值从大到小进行排序即最大元素位于队列的前面。
priority_queue的定义和结构如下
templateclass T,class Container vectorT,class Compare lesstypename Container::value_type
class priority_queue;
T:表示存储在priority_queue中的元素类型。
Container表示底层容器的类型默认为vector。也可以使用其他容器类型如deque。
Compare:表示元素之间的比较函数对象的类型默认为less即按照元素的值进行比较。
priority_queue的内部实现使用了底层容器来存储元素并且只能通过特定的函数来访问和操作元素。
priority_queue常用函数
函数 描述 时间复杂度
push(x) 在队尾插入到优先队列中 O(logn)
pop() 弹出优先队列中的顶部元素 O(logn)
top() 返回优先队列中的顶部元素 O(1)
empty() 检查优先队列是否为空 O(1)
size() 返回优先队列中元素的个数 O(1)
优先队列是个十分重要的数据结构
优先队列修改比较函数的方法
1.仿函数方法
struct Compare
{bool operator()(int a,int b){//自定义的比较函数按照逆序排列return ab;}
};
int main()
{std::priority_queueint,std::vectorint,Comparepq;
}
2.自定义比较函数
auto compare [](int a,int b)
{return ab;
};
std::priority_queueint,std::vectorint,decltype(compare)pq(compare);
deque双端队列
deque双端队列是一种容器它允许在两端进行高效的插入和删除操作。deque是由一系列连续的存储块缓冲区组成的每个存储块都存储了多个元素。这使得deque能够在两端进行快速的插入和删除操作而不需要移动其他元素。
常用的函数
函数 描述 时间复杂度
push_back(x) 在尾部插入元素x 平摊O(1)
push_front(x) 在头部插入元素x 平摊O(1)
pop_front() 弹出头部元素 O(1)
pop_back() 弹出尾部元素 O(1)
front() 返回头部元素 O(1)
back() 返回尾部元素 O(1)
empty() 检查deque是否为空 O(1)
size() 返回deque中元素的个数 O(1)
clear() 清空deque中的所有元素 O(1)
例题1
题目描述
ZZB银行有两个窗口VIP窗口和普通窗口VIP用户进入VIP窗口排队剩下的进入普通窗口排队。现有M次操作操作有四种类型如下
IN name v表示一名叫name的用户到VIP窗口排队
OUT v:表示VIP窗口队头的用户离开排队
IN name N表明一名叫name的用户到普通窗口排队
OUT N表明普通窗口队头的用户离开排队
求M次操作后VIP窗口队列和普通队列中的姓名
输入描述
第一行是一个整数M1M1000,表示一共有M次操作
第二行到第M1行输入操作格式如下
IN name v
OUT v
IN name N
OUT N
输出描述
输出M次操作后VIP窗口队列和普通队列中的姓名从头到尾先输出VIP窗口队列后输出普通窗口队列。
示例输入输出
输入
5
IN xiaoming N
IN adel V
IN LAOZHAO N
OUT N
IN CLZ V
输出
adel
CLZ
LAOZHAO
解
#includeiostream
#includestring
#includequeue
using namespace std;int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int m; cin m;queuestringV, N;while (m--){string op; cin op;if (op IN){string name,q; cin nameq;if (q V){V.push(name);}else{N.push(name);}}else{string q; cin q;if (q V){V.pop();}else{N.pop();}}}while (V.size()){cout V.front() endl;V.pop();}while (N.size()){cout N.front() endl;N.pop();}return 0;
}
例题2
题目描述
在一个果园里多多已经将所有的果子打下来了而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。
每一次合并多多可以把两堆果子合到一起消耗的体力等于两堆果子重量之和。可以看出所有的果子经过n-1次合并之后就剩下一堆了多多在合并果子是总共消耗的体力等于每次合并消耗体力之和。
设计合并次序方案获取体力消耗最小值。
输入描述
输入两行
第一行是一个整数n(1n10^4)表示果子的种类数。
第二行包含n个整数表示每种果子的数量。
输出描述
输出一个整数体力最小值输入数据保证这个值小于2^33.
输入输出示例
输入
3
1 2 9
输出
15
解
#includeiostream
#includestring
#includequeue
#includevector
using namespace std;
using LL long long;int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int n; cin n;priority_queueLL, vectorLL,greaterLL pq;for (int i 1; i n; i){LL x; cin x;pq.push(x);}LL ans 0;while (pq.size() 2){LL x pq.top(); pq.pop();LL y pq.top(); pq.pop();ans x y;pq.push(x y);}cout ans endl;return 0;
}
