1014 Waiting in Line 队列操作
2023-09-11 14:17:55 时间
目录
题目
题目链接:1014 Waiting in Line (PAT (Advanced Level) Practice)
输入样例
2 2 7 5
1 2 6 4 3 534 2
3 4 5 6 7
输出样例
08:07
08:06
08:10
17:00
Sorry
提交结果截图
带详细注释的源代码
代码参考了博文——PTA 1014 Waiting in Line (30分) 解题思路及满分代码
#include <iostream>
#include <queue>
#include <cstdio>
using namespace std;
#define open_time 8*60
#define close_time 17*60
struct Customer
{
int process_time;
int start_time;
int finish_time;
}customer[1001];
int main()
{
int N,//the num of windows, <=20
M,//max capacity of each line, <=10
K,//the num of customers, <=1000
Q;//the num of queries, <=1000
cin>>N>>M>>K>>Q;
queue<Customer>Window[20];
int queries[1001];
for(int i = 1; i <= K; i++)
cin>>customer[i].process_time;
for(int i = 0; i < Q; i++)
cin>>queries[i];
for(int i = 1; i <= K; i++)
{
int window_num;
if(i <= N*M)
{
window_num = (i-1)%N;//window num start from 0 while customer num start from 1
if(i <= N)//their start time = open time
customer[i].start_time = open_time;
else
{ //get the previous customer's infomation
Customer pre_customer = Window[window_num].back();
customer[i].start_time = pre_customer.finish_time;
}
}
else
{
window_num = 0;//window num start from 0
for(int j = 1; j < N; j++)//get the head customers's leaving time
if(Window[j].front().finish_time < Window[window_num].front().finish_time)
window_num = j;
Customer pre_customer = Window[window_num].back();get the head customer
Window[window_num].pop();
customer[i].start_time = pre_customer.finish_time;
}
customer[i].finish_time = customer[i].start_time + customer[i].process_time;
Window[window_num].push(customer[i]);
}
//solve the queries
for(int i = 0; i < Q; i++)
{
if(customer[queries[i]].start_time >= close_time)//if the bank is closed
cout<<"Sorry"<<endl;
else//output the finishing time
printf("%02d:%02d\n", customer[queries[i]].finish_time/60, customer[queries[i]].finish_time%60);
}
return 0;
}
相关文章
- 【BZOJ1047】[HAOI2007]理想的正方形(单调队列,动态规划)
- 【BZOJ2806】Cheat(后缀自动机,二分答案,动态规划,单调队列)
- 【CF944G】Coins Exhibition DP+队列
- 栈和队列,双端队列,如何用链表实现双端队列,如何用双端队列实现栈和队列
- Java 并发编程学习笔记 理解CLH队列锁算法
- Cow Hopscotch (单调队列 + DP)
- 支军队正在进行阅兵前的训,训陈前队列排队是一个难题。该队列是一个n*n的方阵,排队要求是后一排的最低的不比前一排最高的低,同时要求偶数行从小到大排列,奇数行从大到小排列(行数从第0行开始,O为偶数)。输λn及η*n个身高数据〈身高数据为整型),按要求处理后输岀 n队列身高数据(每个身高数据占4个字符宽度)。
- 使用消息队列的理由
- 栈和队列判断回文数
- 【Java数据结构与算法】Java如何实现环形队列
- 多线程之三(【多线程案例】单例模式+阻塞式队列+定时器+线程池)
- 【数字IC验证快速入门】14、SystemVerilog学习之基本语法1(数组、队列、结构体、枚举、字符串...内含实践练习)
- RabbitMQ如何保证队列里的消息99.99%被消费?