当前位置:首页 > 模拟 > 正文
洛谷P1844阅览室[NOI导刊]
692+

题目大意:在T时间内有n个人去图书馆借书,请根据借阅关系、时间关系,统计一下借阅总次数。

题目描述

一个阅览室每天都要接待大批读者。阅览室开门时间是O,关门时间是T。每位读者的到达时间都不一样,并且想要阅读的刊物不超过5本。每位读者心里对自己想看的刊物都有一个排位,到达之后他会先去找自己最想看的刊物,如果找不到则去找其次想看的刊物。如果找不到任何他想看的刊物,他会开始等待,直到有一本以上的他想看的刊物被人放回原处。当然,他会先去拿其中自己最想看的刊物。当他看完某一本刊物后,就把它放回原处,接着去找自己没看过的最想看的刊物。如此下去,直到看完所有他想看的刊物为止。矛盾出现在两个人同时想要拿同一本刊物的时候。阅览室为了避免读者之间出现争执,作了一个规定,读者每次在开始等待时先去服务台做一次登记。如果两个人都同时想要一本刊物,那么先登记的读者将得到这本刊物。如果两个人同时登记,那么先到达阅览室的读者将得到刊物。没得到的人就只能去找其他的刊物看。阅览室关门时,所有读者都将被强迫离开阅览室,不再允许继续阅读。

现在阅览室想做一个统计调查,你被要求写一个程序来模拟这个过程计算出所有刊物被阅读的总次数。当某个读者开始阅读某本刊物时,该刊物的被阅读次数就加1,无论这本刊物最后有没有被读完。

输入输出格式

输入格式

输入包括了多个测试数据。每个测试数据开头是两个整数T和n(1≤n≤100),分别表示图书馆关门时间和读者总数。接下来按照读者的到达时间先后依次给出了每位读者的具体描述。每个读者描述开头是一个整数t(0≤t<T),表示该读者到达时间。接下来一行开头是一个整数k(1≤k≤5),表示该读者想要看的刊物数目。之后跟着2k个整数按照读者想要阅读的刊物的顺序依次给出了刊物的描述。其中第2i-1个整数表示刊物的编号s(0≤s<1000),第2i个整数表示该读者读完这本刊物所需的时间。

输出格式

对于每个测试数据,在单独一行里输出所有刊物被阅读的总次数。

输入输出样例

输入样例 #1

10 4 
1
2 1 4 2 5 
3 
1 2 4 
7 
3 2 2 1 3 3 2 
9 
1 4 2 

输出样例 #1

5

解题思路

用结构体存储人的信息,包括到达时间t、借书时间y、借不到的登记时间x,其中t是不变的,读完一本书就立刻借书,此时就是时间y(借不到下一秒继续借要更新),如果首借不得就登记,此时时间为x,每读完一本书更新一次。

模拟时间一秒一秒过去,重载小于号打擂台找到第一个可以借书的人(时间相同按优先级),能借就借,不能借,他就只能等下一秒继续借,借书时间推迟1秒。

我们可以用哈希记录每一本书借出状态u、每个人借过的书f、每个人正在读哪本书r、每个人是否在读书v,其实v和r可以合并。

需要注意的是时间赋初值,x和y都是到达时间t,因为到达就开始借书、登记。另外,一个人借另外一本书,需要还书,但可能有其他人此时也恰好读完,只是还没轮到他借,所以该时间点读完书的人都要还书。

程序实现

About

坚决不Copy代码!

本文标签:,,,,,,,

洛谷P1844阅览室[NOI导刊]:等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!