PTA 银行排队问题之单队列多窗口服务

假设银行有K个窗口提供服务,窗口前设一条黄线,所有顾客按到达时间在黄线后排成一条长龙。当有窗口空闲时,下一位顾客即去该窗口处理事务。当有多个窗口可选择时,假设顾客总是选择编号最小的窗口。

本题要求输出前来等待服务的N位顾客的平均等待时间、最长等待时间、最后完成时间,并且统计每个窗口服务了多少名顾客。

输入格式:

输入第1行给出正整数N(≤),为顾客总人数;随后N行,每行给出一位顾客的到达时间T和事务处理时间P,并且假设输入数据已经按到达时间先后排好了顺序;最后一行给出正整数K(≤),为开设的营业窗口数。这里假设每位顾客事务被处理的最长时间为60分钟。

输出格式:

在第一行中输出平均等待时间(输出到小数点后1位)、最长等待时间、最后完成时间,之间用1个空格分隔,行末不能有多余空格。

在第二行中按编号递增顺序输出每个窗口服务了多少名顾客,数字之间用1个空格分隔,行末不能有多余空格。

输入样例:

9
0 20
1 15
1 61
2 10
10 5
10 3
30 18
31 25
31 2
3

输出样例:

6.2 17 61
5 3 1
#include <bits/stdc++.h>
using namespace std;
const int maxn = 10100;
typedef long long LL;
struct node
{
    int arrive;
    int cost;
}p[maxn];
int server[20]={0};
int Per[20]={0};
int n,k;
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d%d",&p[i].arrive,&p[i].cost);
        p[i].cost = p[i].cost > 60?60:p[i].cost;
    }
    scanf("%d",&k);
    memset(Per,0,sizeof(Per));
    LL waittime = 0;
    int longwaittime = 0;
    memset(server,0,sizeof(server));
    for(int i=0;i<n;i++)
    {

        int serverid=0;
        for(int j=0;j<k;j++)
        {
            if(server[j]<=p[i].arrive)
            {
                serverid = j;
                break;
            }
            else
            {
                //这个等号卡了我好久
                serverid = server[serverid]<=server[j]?serverid:j;
            }
        }
        if(server[serverid] > p[i].arrive)
        {
            waittime+=(server[serverid]-p[i].arrive);
            longwaittime = max(longwaittime,server[serverid]-p[i].arrive);
            server[serverid] = server[serverid] + p[i].cost;
        }
        else
        {
            server[serverid] = p[i].arrive+p[i].cost;
        }
        Per[serverid]++;
    }
    //的N位顾客的平均等待时间、最长等待时间、最后完成时间,并且统计每个窗口服务了多少名顾客。
    double avewait = (waittime*1.0)/(n*1.0);
    int finishtime = *max_element(server,server+k);
    printf("%.1lf %d %d\n",avewait,longwaittime,finishtime);
    for(int i=0;i<k;i++)
        printf("%d%c",Per[i],i==k-1?'\n':' ');
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏lgp20151222

java与模式读后总结

老规则边看边写书上的代码,磨磨蹭蹭三个多星期终于把一本1000+的java与模式看完了。

1092
来自专栏微服务生态

究竟怎样写代码才算是好代码

今天让我们来谈谈代码吧。代码重要吗?当然,代码就是设计(Jack W.Reeves, 1992);代码是最有价值的交付物。我们需要好代码吗?在给“好代码”下个定...

893
来自专栏诸葛青云的专栏

3分钟读懂C语言函数:这些例子一看就懂!|一键删除账户教学

最近发现,有些小伙伴对C语言的函数有些难以理解,其实呢,C语言的函数很好理解,只不过部分人在学习的时候,没有找到好的例子来类比理解而已。这篇文章会教大家如何去理...

1162
来自专栏java一日一条

编写高质量代码的思考

最近在看《代码大全》,可以说是一本软件开发的百科全书,特别厚,但是干货也很多。平时写代码,代码规范是一个最低的要求(很多老代码连最低要求都达不到),为什么要这样...

972
来自专栏华章科技

入门科普:什么时候要用Python?用哪个版本?什么时候不能用?

Python使用面向对象编程(object-oriented programming,OOP)和构造,你可以像任何其它面向对象的语言一样使用它,譬如Java。

1592
来自专栏WindCoder

网易MySQL微专业学习笔记(六)-内置函数

这个系列属于个人学习网易云课堂MySQL数据库工程师微专业的相关课程过程中的笔记,本篇为其“MySQL数据库对象与应用”中的MySQL数据类型相关笔记。

761
来自专栏互联网杂技

ES2017 异步函数现已正式可用

ES2017标准已于2017年6月份正式定稿了,并广泛支持最新的特性:异步函数。如果你曾经被异步 JavaScript 的逻辑困扰,这么新函数正是为你设计的。 ...

2924
来自专栏iKcamp

翻译连载 | 第 10 章:异步的函数式(上)-《JavaScript轻量级函数式编程》 |《你不知道的JS》姊妹篇

原文地址:Functional-Light-JS 原文作者:Kyle Simpson-《You-Dont-Know-JS》作者 第 10 章:异步的函数式(上)...

2179
来自专栏java一日一条

程序员你为什么这么累【续】:编码习惯之接口定义

工作中,少不了要定义各种接口,系统集成要定义接口,前后台掉调用也要定义接口。接口定义一定程度上能反应程序员的编程功底。列举一下工作中我发现大家容易出现的问题:

1132
来自专栏spring源码深度学习

设计模式——代码如若初相见

设计模式(Design pattern)是一套被反复使用、多数人知晓的、经过分类编目的、代码设计经验的总结。

992

扫码关注云+社区

领取腾讯云代金券