[PAT解题报告] Queueing at Bank
一个银行有K个窗口,每个窗口只能服务一个人,有n个人,达到时间不同,银行开始服务和结束服务的时间是8点到17点,如果17点前到达,但是在排队,最后服务的时间比17点晚是可能的,但是17点以后到达的人就没办法了。给定每个人达到时间和服务的时间,求办理业务的人的平均等待时间。

分析: 这个也是模拟题。其实我们不关心每个人在哪个窗口排队或者服务,我们没有必要记录哪些人在哪个窗口——只要记录哪些人在什么时间被服务,在什么时间服务结束即可。当然需要记录还有多少个窗口。我们用一个“事件控制器”——即表示事件的队列,最初每个人达到事件都放入队列里,然后每个人记录一个服务开始的事件,当服务开始的时候我们自然知道它等了多久,累加等待的事件,然后我们也知道他什么时候离开,这样好把可用窗口个数加1。
总的来说 事件包括
(1) 新来一个人
(2) 开始服务一个人
(3) 服务完成一个人
我们分别把这3个时间放到优先队列里,C++ STL有priority_queue, 我更习惯用multiset,虽然实现不一样,但是功能相仿
我们的事件是维度的pair,总的来说是一个开始时间,和一个持续时间。
我是在人离开的时候把持续时间设置为-1了,因为这一维没用了。
总体流程:
(1) 来一个人,放入临时等待队列里。
(2) 出一个人,可用窗口数加1。
(3) 每次如果等待队列里有人就移出一个到窗口。
更新时间now,另外注意8点和17点的限制就好了。
代码很短。
#include <cstdio>
#include <set>
#include <queue>

using namespace std;

multiset<pair<int,int> > all;
queue<pair<int,int> > q;

const int t8 = 8 * 3600;
const int t17 = 17 * 3600;

int main() {
int m,n;
  for (scanf("%d%d",&n,&m);n;--n) {
    int hh,mm,ss,s;
    scanf("%d:%d:%d%d",&hh,&mm,&ss,&s);
    int temp = hh * 3600 + mm * 60 + ss;
    if (temp <= t17) {
      all.insert(make_pair(temp, s * 60));
    }
  }
  int num = 0, total = 0;
  for (int now = t8;(!all.empty()) || (!q.empty());) {
    if (!all.empty()) {
      if (all.begin()->second >= 0) {
        q.push(*all.begin());
        now = max(now, all.begin()->first);
      }
      else {
        now = all.begin()->first;
        ++m;
      }
      all.erase(all.begin());
    }
        for (;m && (!q.empty()); ++num, --m, q.pop()) {
      total += now - q.front().first;
      all.insert(make_pair(now + q.front().second, -1));
    }
  }
  printf("%.1lf\n",total / 60. / num);
  return 0;
}

原题链接: http://www.patest.cn/contests/pat-a-practise/1017

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
2022-12-30 15:34
广州大学_2023
点赞 评论 收藏
转发
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-30 20:45
门头沟学院_2023
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-22 16:33
重庆工商大学_2024
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议