PTA 银行排队问题之单队列多窗口服务(25 分)

Wesley13
• 阅读 685

银行排队问题之单队列多窗口服务(25 分)

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

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

输入格式:

输入第1行给出正整数N(≤1000),为顾客总人数;随后N行,每行给出一位顾客的到达时间T和事务处理时间P,并且假设输入数据已经按到达时间先后排好了顺序;最后一行给出正整数K(≤10),为开设的营业窗口数。这里假设每位顾客事务被处理的最长时间为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<stdio.h>  
#include<stdlib.h>  
typedef struct node  
{  
    int t, p;//到达时间,处理时间  
}ST;  
ST q[1005];//数组模拟队列  
int main()  
{  
    int l, r, n, k, i;  
    while(~scanf("%d", &n))  
    {  
        l = r = 0;//队列头和尾  
        for(i = 0; i < n; i++)  
        {  
            scanf("%d %d", &q[r].t, &q[r].p);//将输入的数入队列  
            if(q[r].p > 60) q[r].p = 60;//根据题目要求,最大处理时间60  
            r++;  
        }  
        scanf("%d", &k);//k个窗口  
        int sumwait = 0, lenwait = 0, wait = 0;//总的等待时间, 最长的等待时间, 单次等待时间  
        int sum[15] = {0}, winnum[15] = {0};//完成时间,窗口人数  
        while(l < r)  
        {  
            int flag = 0, minn = 99999, imin = 0;//标记变量, 最快的完成时间, 最快完成时间的下标  
            for(i = 0; i < k; i++)//遍历k个窗口  
            {  
                if(sum[i] < q[l].t)//如果队列首位,到达时间比,完成时间大,就代表不需要等待  
                {  
                    sum[i] = q[l].t + q[l].p;//更新完成这个窗口完成的时间  
                    winnum[i]++;//窗口人数加一  
                    flag = 1;//标记一下,代表不需要等待  
                    l++;//队列首位除去  
                    break;//退出循环  
                }  
                if(minn > sum[i])//如果需要等待,就记录各个窗口里最快完成的那个窗口的完成时间,和下标  
                {  
                    minn = sum[i];  
                    imin = i;  
                }  
            }  
            if(!flag)//需要等待  
            {  
                wait = minn - q[l].t;//等待的时间,最快完成的时间减去队列第一个人到达的时间  
                if(lenwait < wait) lenwait = wait;//不断更新等待的最长时间  
                sumwait += wait;//求等待时间的和  
                sum[imin] = minn + q[l].p;//更新对应窗口的完成时间  
                winnum[imin]++;//对应窗口人数++  
                l++;//队列删除首位  
            }  
        }  
        int last = 0;  
        for(i = 0; i < k; i++)  
        {  
            if(last < sum[i]) last = sum[i];//求最大完成时间  
        }  
        printf("%.1lf %d %d\n", 1.0 * sumwait / n, lenwait, last);//输出,平均等待时间, 最长等待时间, 最后完成时间  
        for(i = 0; i < k; i++)  
        {  
            printf("%d", winnum[i]);//输出各个窗口的人数  
            if(i == k - 1) printf("\n");  
            else printf(" ");  
        }  
    }  
    return 0;  
}
点赞
收藏
评论区
推荐文章
blmius blmius
2年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid()或uuid(sep)参数说明:sep布尔值,生成的uuid中是否包含分隔符'',缺省为
Wesley13 Wesley13
2年前
Java日期时间API系列31
  时间戳是指格林威治时间1970年01月01日00时00分00秒起至现在的总毫秒数,是所有时间的基础,其他时间可以通过时间戳转换得到。Java中本来已经有相关获取时间戳的方法,Java8后增加新的类Instant等专用于处理时间戳问题。 1获取时间戳的方法和性能对比1.1获取时间戳方法Java8以前
Stella981 Stella981
2年前
Python之time模块的时间戳、时间字符串格式化与转换
Python处理时间和时间戳的内置模块就有time,和datetime两个,本文先说time模块。关于时间戳的几个概念时间戳,根据1970年1月1日00:00:00开始按秒计算的偏移量。时间元组(struct_time),包含9个元素。 time.struct_time(tm_y
Easter79 Easter79
2年前
Twitter的分布式自增ID算法snowflake (Java版)
概述分布式系统中,有一些需要使用全局唯一ID的场景,这种时候为了防止ID冲突可以使用36位的UUID,但是UUID有一些缺点,首先他相对比较长,另外UUID一般是无序的。有些时候我们希望能使用一种简单一些的ID,并且希望ID能够按照时间有序生成。而twitter的snowflake解决了这种需求,最初Twitter把存储系统从MySQL迁移
Wesley13 Wesley13
2年前
Java线程同步之一
一、线程同步线程同步是指两个并发执行的线程在同一时间不同时执行某一部分的程序。同步问题在生活中也很常见,就比如在麦当劳点餐,假设只有一个服务员能够提供点餐服务。每个服务员在同一时刻只能接待一个顾客的点餐,那么除了正在接待的顾客,其他人只能等待排队。当一个点餐服务完成之后,其他顾客就可以上去进行点餐。从这个例子中可以看到如下几个关注点:点餐服务
Wesley13 Wesley13
2年前
Oracle一张表中实现对一个字段不同值和总值的统计(多个count)
需求:统计WAIT\_ORDER表中的工单总数、未处理工单总数、已完成工单总数、未完成工单总数。表结构:为了举例子方便,WAIT\_ORDER表只有两个字段,分别是ID、STATUS,其中STATUS为工单的状态。1表示未处理,2表示已完成,3表示未完成总数。 SQL:  1.SELECT   2
Wesley13 Wesley13
2年前
Mysql 8.0 忘记密码报错1045办法,skip
1.首先关掉系统服务2.打开命令窗口,用mysqldconsoleskipgranttablessharedmemory可以无密码启动服务,不关闭窗口3.另外开一个管理员窗口打开mysql服务,执行mysql.exeuroot命令,空密码登入系统mysql.exeuroot1
Stella981 Stella981
2年前
Carte作为Windows服务
有一些用例将Carte作为Windows服务运行:当使用命令窗口运行Carte实例时,任何人都会错误地关闭实例并且Carte将关闭。Carte.bat命令窗口与调用批处理文件的用户会话相关联,需要保持登录状态。使用Windows服务,您可以在计算机启动时启动Carte服务,并将其配置为在崩溃后重新启动。完成以下说明后,您可
常用限流算法详解
一、有哪些常用的限流算法1.固定窗口限流;2.滑动窗口限流;3.漏桶算法限流;4.令牌桶算法限流。二、4种限流算法介绍1.固定窗口限流举例说明:假设时间窗口大小为5s,则0到5s为第一个窗口,5到10s为第二个窗