上海计算机学会2024年9月月赛C++乙组T2银行服务
发布时间
阅读量：
阅读量
银行服务
内存限制: 256 Mb时间限制: 1000 ms
题目描述
在某家金融机构中设有一个服务窗口，在处理多笔业务请求时（如有多位顾客前来办理取款），这些顾客需依次按到达时间排队等候。
在营业期间，发生了 n 件事，记录如下：
- 一位新客户携带资金x元前来办理业务，并将此记录为+ x。
- 首位客户的存款已全部取出，并予以记录。
- 请经理确认当前仍在银行客户的最高存款额，并记录为？
给定记录的事件序列，请为每个查询记录计算并输出查询结果。
输入格式
- 单一整数 n 代表事件数量
- 共有 n 条目 每条目对应一个事件
- 所有事件的标识符只能是 + - 或 ?
- 当标识符为 + 后必定跟随一个数值 x
- 共有 n 条目 每条目对应一个事件
输出格式
- 若干行：对每个查询，计算留在银行中的客户的最高取款金额。
数据范围
- 30% 的数据，1≤n≤1000
- 60% 的数据，1≤n≤20000
- 100% 的数据，1≤n≤300,000
- 1≤x≤1,000,000,000
样例数据
输入:
6
+ 10
+ 1
+ 5
??
输出:
10
5
解析：
使用优先队列保存取款人信息，模拟，详见代码：
#include<bits/stdc++.h>
using namespace std;
int n;
struct node {
int a, b; //取款金额，编号
};
//重载小于运算符，使优先队列中取款金额高的排前面
bool operator < (node x, node y) {
return x.a < y.a;
}
int cnt = 0; //取款人编号
int p = 1; //在取款中第一个人的编号
priority_queue <node, vector<node>> pq; //优先队列
int main() {
cin >> n;
for(int i = 1; i <= n; i++) { //枚举n次操作
char op;
node t;
cin >> op;
if (op == '+') { //加号
cnt++;
cin >> t.a; //输入取款数量
t.b = cnt; //记录编号
pq.push(t);//进入优先队列
} else if (op == '-') { //取款离开
p++;//在取款的第一个人变成下一个人
} else {//查询
//当前队头人如果离开，则弹出队头
while (!pq.empty() && pq.top().b < p) {
pq.pop();
}
if (pq.empty()) { //如果没有取款人了
cout << 0 << "\n";
} else { //否则输出队头（即取款金额最高的人）的取款金额
cout << pq.top().a << "\n";
}
}
}
return 0;
}全部评论 (0)
还没有任何评论哟~