九度OJ 1326:Waiting in Line(排队) (模拟)

2024-04-02 02:08

本文主要是介绍九度OJ 1326:Waiting in Line(排队) (模拟),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

时间限制:1 秒

内存限制:32 兆

特殊判题:

提交:220

解决:64

题目描述:

Suppose a bank has N windows open for service. There is a yellow line in front of the windows which devides the waiting area into two parts. The rules for the customers to wait in line are:

  • The space inside the yellow line in front of each window is enough to contain a line with M customers. Hence when all the N lines are full, all the customers after (and including) the (NM+1)st one will have to wait in a line behind the yellow line.
  • Each customer will choose the shortest line to wait in when crossing the yellow line. If there are two or more lines with the same length, the customer will always choose the window with the smallest number.
  • Customer[i] will take T[i] minutes to have his/her transaction processed.
  • The first N customers are assumed to be served at 8:00am.

Now given the processing time of each customer, you are supposed to tell the exact time at which a customer has his/her business done.

For example, suppose that a bank has 2 windows and each window may have 2 custmers waiting inside the yellow line. There are 5 customers waiting with transactions taking 1, 2, 6, 4 and 3 minutes, respectively. At 08:00 in the morning, customer1 is served at window1 while customer2 is served at window2. Customer3 will wait in front of window1 and customer4 will wait in front of window2. Customer5 will wait behind the yellow line.

At 08:01, customer1 is done and customer5 enters the line in front of window1 since that line seems shorter now. Customer2 will leave at 08:02, customer4 at 08:06, customer3 at 08:07, and finally customer5 at 08:10.

输入:

Each input file contains one test case. Each case starts with a line containing 4 positive integers: N (<=20, number of windows), M (<=10, the maximum capacity of each line inside the yellow line), K (<=1000, number of customers), and Q (<=1000, number of customer queries).

The next line contains K positive integers, which are the processing time of the K customers.

The last line contains Q positive integers, which represent the customers who are asking about the time they can have their transactions done. The customers are numbered from 1 to K.

输出:

For each of the Q customers, print in one line the time at which his/her transaction is finished, in the format HH:MM where HH is in [08, 17] and MM is in [00, 59]. Note that since the bank is closed everyday after 17:00, for those customers who cannot be served before 17:00, you must output "Sorry" instead.

样例输入:
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

思路:

模拟题,排队题当然数据结构用队列比较好。

用C语言太苦逼了,还要自己写一个队列,还是C++比较好,以后要用C++了。

需要注意的是:即使是17点之前开始办业务,17点之后仍然没有办完就是sorry。


代码:

#include <stdio.h>
#include <stdlib.h> #define N 21
#define M 11
#define K 1001typedef struct node1 {int proc;int begin;
} Cust;typedef struct node2 {Cust *cust[M];int front;int rear;
} Queue;int isEmpty(Queue *q)
{return (q->front == q->rear);
}   int isFull(Queue *q)
{   return (q->front == (q->rear+1)%M);
}int countQueue(Queue *q)
{       return (q->rear + M - q->front) % M;
}           void push(Queue *q, Cust *val)
{       q->cust[q->rear] = val;q->rear = (q->rear+1)%M;
}           Cust *pop(Queue *q)
{       int front = q->front;q->front = (q->front+1)%M;return q->cust[front];
}Cust *top(Queue *q)
{return q->cust[q->front];
}int main(void)
{int n, m, k, q, i, j;Queue *queue[N];Cust *cust[K];int query[K];int maxTime = (17-8)*60;while (scanf("%d%d%d%d", &n, &m, &k, &q) != EOF){for (i=0; i<n; i++){queue[i] = (Queue *)malloc(sizeof(Queue));queue[i]->front = queue[i]->rear = 0;}for (i=0; i<k; i++){cust[i] = (Cust *)malloc(sizeof(Cust));scanf("%d", &cust[i]->proc);cust[i]->begin = maxTime+1;}for (i=0; i<q; i++)scanf("%d", &query[i]);// init stateint inQueue = 0;int outQueue = k;for (i=0; i<m; i++){for (j=0; j<n; j++){inQueue = i*n + j;if (inQueue >= k)break;if (i == 0)cust[inQueue]->begin = 0;push(queue[j], cust[inQueue]);}if (inQueue >= k)break;}inQueue = (m*n <= k) ? (inQueue+1) : inQueue;outQueue = k - inQueue;//printf("inQueue=%d, outQueue=%d, k=%d\n", inQueue, outQueue, k);// simulate the whole processint time;for (time=0; time<=maxTime; time++){for (i=0; i<n; i++){if (isEmpty(queue[i]))break;Cust *c = top(queue[i]);if (c->begin + c->proc == time){pop(queue[i]);if (outQueue > 0){ push(queue[i], cust[k-outQueue]);outQueue --;}if (!isEmpty(queue[i])){top(queue[i])->begin = time;//printf("i=%d, time=%d\n", i, time);} }}if (isEmpty(queue[0]))break;}   for (i=0; i<q; i++) {int id = query[i] - 1;int endTime = cust[id]->begin + cust[id]->proc;if (endTime > maxTime)printf("Sorry\n");elseprintf("%02d:%02d\n", 8 + endTime/60, endTime%60);}}return 0;
}
/**************************************************************Problem: 1326User: liangrx06Language: CResult: AcceptedTime:10 msMemory:916 kb
****************************************************************/


这篇关于九度OJ 1326:Waiting in Line(排队) (模拟)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/868708

相关文章

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

usaco 1.2 Transformations(模拟)

我的做法就是一个一个情况枚举出来 注意计算公式: ( 变换后的矩阵记为C) 顺时针旋转90°:C[i] [j]=A[n-j-1] [i] (旋转180°和270° 可以多转几个九十度来推) 对称:C[i] [n-j-1]=A[i] [j] 代码有点长 。。。 /*ID: who jayLANG: C++TASK: transform*/#include<

hdu4431麻将模拟

给13张牌。问增加哪些牌可以胡牌。 胡牌有以下几种情况: 1、一个对子 + 4组 3个相同的牌或者顺子。 2、7个不同的对子。 3、13幺 贪心的思想: 对于某张牌>=3个,先减去3个相同,再组合顺子。 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOExcepti

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟)

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟) 题目描述 给定一个链表,链表中的每个节点代表一个整数。链表中的整数由 0 分隔开,表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点,新节点的值为原区间内所有节点值的和。合并后,需要移除所有的 0,并返回修改后的链表头节点。 思路分析 初始化:创建一个虚拟头节点

每日一题|牛客竞赛|四舍五入|字符串+贪心+模拟

每日一题|四舍五入 四舍五入 心有猛虎,细嗅蔷薇。你好朋友,这里是锅巴的C\C++学习笔记,常言道,不积跬步无以至千里,希望有朝一日我们积累的滴水可以击穿顽石。 四舍五入 题目: 牛牛发明了一种新的四舍五入应用于整数,对个位四舍五入,规则如下 12345->12350 12399->12400 输入描述: 输入一个整数n(0<=n<=109 ) 输出描述: 输出一个整数

【算法专场】模拟(下)

目录 前言 38. 外观数列 算法分析 算法思路 算法代码 1419. 数青蛙 算法分析 算法思路 算法代码  2671. 频率跟踪器 算法分析 算法思路 算法代码 前言 在前面我们已经讲解了什么是模拟算法,这篇主要是讲解在leetcode上遇到的一些模拟题目~ 38. 外观数列 算法分析 这道题其实就是要将连续且相同的字符替换成字符重复的次数+

模拟实现vector中的常见接口

insert void insert(iterator pos, const T& x){if (_finish == _endofstorage){int n = pos - _start;size_t newcapacity = capacity() == 0 ? 2 : capacity() * 2;reserve(newcapacity);pos = _start + n;//防止迭代

PHP实现二叉树遍历(非递归方式,栈模拟实现)

二叉树定义是这样的:一棵非空的二叉树由根结点及左、右子树这三个基本部分组成,根据节点的访问位置不同有三种遍历方式: ① NLR:前序遍历(PreorderTraversal亦称(先序遍历)) ——访问结点的操作发生在遍历其左右子树之前。 ② LNR:中序遍历(InorderTraversal) ——访问结点的操作发生在遍历其左右子树之中(间)。 ③ LRN:后序遍历(PostorderT

Debugging Lua Project created in Cocos Code IDE creates “Waiting for debugger to connect” in Win-7

转自 I Installed Cocos Code IDE and created a new Lua Project. When Debugging the Project(F11) the game window pops up and gives me the message waiting for debugger to connect and then freezes. Also a

1 模拟——67. 二进制求和

1 模拟 67. 二进制求和 给你两个二进制字符串 a 和 b ,以二进制字符串的形式返回它们的和。 示例 1:输入:a = "11", b = "1"输出:"100"示例 2:输入:a = "1010", b = "1011"输出:"10101" 算法设计 可以从低位到高位(从后向前)计算,用一个变量carry记录进位,如果有字符没处理完或者有进位,则循环处理。两个字符串对