PAT 解题报告 1014. Waiting in Line (30) | Sigmainfy 烟客旅人
模拟银行排队处理业务的逻辑, 假设银行有N个窗口, 每个窗口黄线以内允许排M个人, 总共有K个客户, 每个客户的业务处理时间也知道, 按照题目的规则, 问每个客户自己的业务处理完成的时间.
算法分析：
基本上是一个模拟题, 每个窗口都是一个queue (大小就是M或者小于M), 想清楚下面两点就可以做了:
(1) 每个窗口队列都设置一个时间代表处理完该队列最后一个客户的时候的时间
(2) 每个窗口队列都设置一个时间代表处理完该队列第一个客户还需要多少时间
那么如果总的客户K < N*M的话只利用(1)就完成了所有客户处理时间的计算, 因为这种情况下, 对于这K的客户, 每个客户在哪个窗口, 在哪个窗口队列中的哪个位置的先后顺序都是确定的.
如果K > N*M那么会有一些客户站在黄线以外, 对于前面的那些N*M个用户, 他们的处理完毕的时间其实还是一样确定的, 但对黄线以外的每个客户, 那么我们需要利用(2)的信息每次找到最快处理完的那个窗口, 因为这样那个窗口队列就是第一个变短的队列, 接下来第一个黄线以外的客户就应该排在那个队里的最后一位, 再利用(1)的信息， 该客户的处理完毕的时间也就随之确定. (还有注意这种情况下, 每个窗口队列其实都是保持长度为M的.)
关键点： 确定每个客户应当排在哪个窗口队列的第几个位置.
注意点：
对于那些无法在17:00点之前被处理的客户输出sorry, 这句话不要理解成一定要在17:00之前完成业务的处理, 比如, 某个客户在16:54的是开始处理他的业务, 在17:37分的时候结束业务处理, 那么对于这个客户, 还是应该输出17:37而不是sorry.
Read full article from PAT 解题报告 1014. Waiting in Line (30) | Sigmainfy 烟客旅人
No comments:
Post a Comment