环保公司网站模版,西部数码装wordpress,上海建筑网站大全,淘宝店铺网站策划书queue队列
queue是一种先进先出的数据结构。它提供了一组函数来操作和访问元素#xff0c;但它的功能相对较简单#xff0c;queue函数的内部实现了底层容器来存储元素#xff0c;并且只能通过特定的函数来访问和操作元素。
queue函数的常用函数
1.push()函数#xff1a;…queue队列
queue是一种先进先出的数据结构。它提供了一组函数来操作和访问元素但它的功能相对较简单queue函数的内部实现了底层容器来存储元素并且只能通过特定的函数来访问和操作元素。
queue函数的常用函数
1.push()函数 在队尾插入元素
2.pop() 函数弹出队首元素
3.front() 函数 返回队首元素
4.back()函数返回队尾元素
5.empty()函数检查队列是否为空
6.size()函数返回队列元素的个数
priority_queue优先队列
priority_queue函数与普通队列不同priority_queue函数中的元素是按照一定的优先级进行排序的。默认情况下priority_queue按照元素的大小的值由大到小进行排序的即top()一定是最大的。priority_queue的内部实现了使用底层容器来存储元素并且只能通过特定的函数来访问和操作元素。
priority_queue函数的常用函数
1.push()函数将元素插入到优先队列中
2.pop()函数退回优先队列中的顶部元素
3.top()函数返回优先队列中的顶部元素
4.empty()函数检查优先队列是否为空
5.size()函数返回优先队列中元素的个数
优先队列修改比较函数的方法
示例1
struct Compare {bool operator()(int a, int b) {return a b;}
};int main() {std::priority_queueint, std::vectorint, Compare pq;return 0;
}
示例2
auto Compare [](int a, int b) {return a b;};
std::priority_queueint, std::vectorint, decltype(compare) pq(compare);
注意如果优先队列比较简单可以直接使用greaterT来修改比较方法。
priority_queueint,vectorint,greaterint pq;
std::greater函数对象定义在functional头文件中。
deque双端队列
deque是一种容器它允许在两端进行高效的插入和删除操作。deque是由一系列连续的存储块缓冲区组成的每个存储块都存储了多个元素这deque函数能够在两端快速的插入和删除操作而不需要移动其他元素。
deque函数的常用函数
1.push_back函数在尾部插入元素
2.push_front函数在头部插入元素
3.pop_back函数弹出尾部元素
4.front函数返回头部元素
5.back函数返回尾部元素
6.empty函数检查deque是否为空
7.size函数返回deque中的元素个数
8.clear函数清空deque中的所有元素
例题讲解
题目一
CLZ银行问题
题目描述
CLZCLZ 银行只有两个接待窗口VIPVIP 窗口和普通窗口VIPVIP 用户进入 VIPVIP 窗口排队剩下的进入普通窗口排队。现有 MM 次操作操作有四种类型如下
IN name V表示一名叫 name 的用户到 VIPVIP 窗口排队OUT V表示 VIPVIP 窗口队头的用户离开排队IN name N表示一名叫 name 的用户到普通窗口排队OUT N表示普通窗口队头的用户离开排队
求 MM 次操作结束后 VIPVIP 窗口队列和普通窗口队列中的姓名。
输入描述
第一行是一个整数 M1≤M≤1000M1≤M≤1000表示一共有 MM 次操作。
第二行到第 M1M1 行输入操作格式如下
IN name VOUT VIN name NOUT N
输出描述
输出 MM 次操作后 VIPVIP 窗口队列和普通窗口队列中的姓名从头到尾先输出 VIPVIP 窗口队列后输出普通窗口队列。
输入输出样例
示例 1 输入 5
IN xiaoming N
IN Adel V
IN laozhao N
OUT N
IN CLZ V输出 Adel
CLZ
laozhao运行限制
最大运行时间1s最大运行内存: 128M
题解
#includeiostream
#includealgorithm
#includevector
int mian() {//输入输出同步流ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);//输入Mint M; cin M;queuestring V, N;//遍历while (M--) {//输入opopIN表示用户到窗口排队string op; cin op;//判断op是否等于INif (op IN) {//输入nmae表示用户姓名//输入qqV表示用户到VIP窗口排队string name,q; cin name q;//判断q是否等于Vif (q V) V.push();//如果qV则在name之后插入元素velse N.push();//否则其判断对象就为N}//如果q不等于与INelse {//输入qqV表示用户到VIP窗口排队string q; cin q;//判断q是否等于Vif (q V) V.pop();//如果qV则弹出队首元素else N.pop();//否则其判断对象就为N}}//遍历while (V.size()) {//定义原始数组大小//输出队首元素cout V.front() endl;//弹出队首元素V.pop;}//同理while (N.size()) {cout N.front() endl;N.pop();}return 0;
}题目二
合并果子
题目描述
在一个果园里多多已经将所有的果子打了下来而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。
每一次合并多多可以把两堆果子合并到一起消耗的体力等于两堆果子的重量之和。可以看出所有的果子经过 n−1n−1 次合并之后就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。
因为还要花大力气把这些果子搬回家所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为 11并且已知果子的种类数和每种果子的数目你的任务是设计出合并的次序方案使多多耗费的体力最少并输出这个最小的体力耗费值。
例如有 33 种果子数目依次为 129129。可以先将 1、21、2 堆合并新堆数目为 33耗费体力为 33。接着将新堆与原先的第三堆合并又得到新的堆数目为 1212耗费体力为 1212。所以多多总共耗费体力 3121531215。可以证明 1515 为最小的体力耗费值。
输入描述
输入两行。
第一行是一个整数 n(1≤n≤104)n(1≤n≤104)表示果子的种类数。
第二行包含 nn 个整数用空格分隔第 ii 个整数 ai(1≤ai≤2×104)ai(1≤ai≤2×104) 是第 ii 种果子的数目。
输出描述
输出一个整数也就是最小的体力耗费值。输入数据保证这个值小于 231231。
输入输出样例
示例 1 输入 3
1 2 9 输出 15 运行限制
最大运行时间1s最大运行内存: 128M
题解
#includeiostream
#includealgorithm
#includevector
using namespace std;
using ll long long;
int main() {//同步流ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);//水果种类数ll n; cin n;priority_queue ll, 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;
}
