PAT 解题报告 1026. Table Tennis (30)

题目描述:

题目是说一个乒乓球俱乐部有N个球桌, 标号从1到N, 有人来玩的时候就依照标号把标号最小的那个桌子分配给他玩, 如果所有桌子都满了的话, 那么玩家要排队等, 等到有桌子空出来的时候, 有两种情况(1) 如果这张桌子不是VIP桌子, 那么这张桌子分配个排队中的第一个玩家(2) 如果这样桌子是VIP的桌子, 那么这张桌子优先分配给排队中的第一个vip玩家, 如果没有vip玩家, 那么就分配给排队中的第一个人. 每个玩家打球的时间不能超过2个小时.

算法分析:

略微复杂的模拟题而已. 按照题目进行模拟, 存一个table的列表, 一个玩家的列表, 一个vip的列表,要确定, 每次处理的case是哪个桌子(table)分配给哪个玩家(player), 那么分四种情况:

(1) 第一个空闲出来的桌子是VIP的桌子, 排队中的第一个玩家是VIP: 桌子分配他就行了

(2) 第一个空闲出来的桌子是VIP的桌子, 排队中的第一个玩家不是VIP: 那么在之前保存的vip列表中寻找第一个vip,看是不是存在vip且这个vip达到的时间比这种桌子空出来的时间早, 如果早的话, 那么这个桌子应该分配给这个vip, 否则该vip桌子还是分配给第一个玩家.

(3) 第一个空闲出来的桌子不是VIP的桌子, 排队中的第一个玩家是VIP: 那么这个时候要检查一下这个vip排队期间是不是在这张桌子空出来之前是不是有其他vip桌子空出来了,如果有, 那么这个vip玩家其实应该会分配到这个vip桌子, 而不是空出来的桌子,也就是说, 当有多个乒乓球桌子空闲时,vip玩家要是到了的话会使用最小id的vip球台,而不是最小id的球台. (这个是这个题目的坑点之一)

(4) 第一个空闲出来的桌子不是VIP的桌子, 排队中的第一个玩家不是VIP: 桌子分配他就行了

分四种情况决定好了本次哪个桌子分配给哪个玩家的时候,更新对应的队列的数据结构的信息. 进行下一次分配, 知道所有的玩家都分配好.

注意点:

这个题目最大的坑点就是:在情况(3)中,当有多个乒乓球桌子空闲时,vip玩家要是到了的话会使用最小标号的vip球桌,而不是最小标号的球台. 还有注意每个玩家最多玩两个小时.

(全文完,原创文章,转载时请注明作者和出处)


(转载本站文章请注明作者和出处 烟客旅人 sigmainfy — http://www.sigmainfy.com,请勿用于任何商业用途)

Written on July 31, 2013