标题:关于用队列解决排队时间问题
只看楼主
xiaohuo66
Rank: 1
等 级:新手上路
帖 子:51
专家分:0
注 册:2020-11-1
结帖率:88.89%
已结贴  问题点数:20 回复次数:3 
关于用队列解决排队时间问题
核酸检测
疫情期间某核酸检测机构有M个服务窗口。因防疫需要,所有人按到达时间顺序排成一个队列,在黄线后面间隔1米等候,有窗口空闲时队首的人上前接受检测。
假设每个人进行检测需要K分钟,已知一天中N个人的到达时间,请你计算平均每个人需要等待多长时间。
注意,该机构工作时间是8点到17点。任何提前到达的人将不得不排队等待到08:00(计入等待时间)。而任何晚到的人(在17:00或之后)将不会得到服务,也不会被计算在平均值中。
 
输入:
正整数 N <= 10000:一天中检测的人数。
正整数 M <= 10:窗口的个数。
正整数 K <= 59:每个人进行检测需要的分钟数。
接下来N行,每行一个时间,表示每个人到达的时间。时间格式为:HH:MM。
输入时间保证合法,且到的早的人在前,到得晚的人在后。
  
输出:一个浮点数,精确到小数点后两位,平均每个人等待的分钟数。
示例:
(输入)7
(输入)2
(输入)10
(输入)07:55
(输入)07:59
(输入)08:00
(输入)08:00
(输入)08:01
(输入)16:59
(输入)17:00
(输出)7.5
(说明)第一个人等待5分钟,第二个人等待1分钟,第三个人等待10分钟,第四个人等待10分钟,第五个人等待19分钟,第六个人等待0分钟,第7个人来晚了不计数。(5+1+10+10+19+0)/6=7.5。
搜索更多相关主题的帖子: 时间 窗口 检测 队列 输入 
2021-09-26 11:39
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:507
帖 子:8890
专家分:53117
注 册:2011-1-18
得分:20 
题目说“精确到小数点后两位”
又说“(输出)7.5”
自相矛盾了吧,应该输出 7.50

程序代码:
#include <cstdio>
#include <algorithm>

// 考虑极限情况,即 10000个人 同时在 00:00 到达检测机构,检测机构只有1个窗口,检测一个人需要59分钟
// 那么总等待时间是 (8*60)*10000 + (10000-1)*59*10000/2 = 2954505000(分钟)
// log(2954505000)/log(2) = 31.46,也就是总等待时间需要一个至少 32bits 有效位的类型

int main( void )
{
    unsigned n, m, k;
    scanf( "%u%u%u", &n, &m, &k );

    unsigned count = 0; // 人数
    unsigned wait = 0; // 等待时间(单位:分钟)
    unsigned ws[10] = { 8*60, 8*60, 8*60, 8*60, 8*60, 8*60, 8*60, 8*60, 8*60, 8*60 }; // 题目交代“工作时间是8点到17点”
    for( unsigned i=0; i!=n; ++i )
    {
        unsigned hh, mm;
        scanf( "%u:%u", &hh, &mm );
        unsigned tp = hh*60 + mm;

        if( tp < 17*60 ) // 题目要求“任何晚到的人(在17:00或之后)将不会得到服务”
        {
            ++count;

            // 取最先结束的一个窗口
            unsigned& r = *std::min_element( ws, ws+m );
            if( tp >= r )
            {
                r = tp + k;
            }
            else
            {
                wait += r - tp;
                r += k;
            }
        }
    }

    printf( "%.2f\n", count==0?0.0:wait*1.0/count );
}
2021-09-26 12:25
xiaohuo66
Rank: 1
等 级:新手上路
帖 子:51
专家分:0
注 册:2020-11-1
得分:0 
回复 2楼 rjsp
谢谢谢谢  这得是打了多少年代码 打出的代码风格 佩服佩服
2021-09-26 15:01
小菜鸡我最菜
Rank: 1
等 级:新手上路
帖 子:2
专家分:4
注 册:2020-3-19
得分:0 
回复 2楼 rjsp
怎么没有点赞
2021-10-08 11:00



参与讨论请移步原网站贴子:https://bbs.bccn.net/thread-506982-1-1.html




关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.015336 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved