某乒乓球场每天服务时间是8:00 -- 21:00
有·K
个桌子(编号 1-K
),其中M
个为会员预留某一天,有N
个玩家要来打球给出了他们的到达时间,玩耍时间和他们是否是会员,要求输絀这些玩家的 到达时间
开始被服务时间 玩耍时间。输出每个桌子服务的人数
-
21:00
及之后到来的玩家无法被服务,这些玩家不用考虑;
- 由于排隊等待导致
21:00
前还未能被服务的玩家也要在输出中排除;
- 每个乒乓球求桌子限制最多一次服务
2
个小时;
- 所有的输出顺序要
按照玩家开始被服務时间
的先后顺序
- vip玩家的服务优先级高于普通玩家。当没有会员来时vip桌子也为普通用户服务。这个的具体理解我在思路中细说
说实話这个题目难度不高,无非就是先来先服务也就是所有玩家按照到达的先后顺序排序然后逐个处理,只不过vip可以" 插队 " 就导致分类讨论比較复杂一点
- 创建结构体
Player
保存玩家的 到达时间、开始被服务时间、玩耍时间、是否是会员。
- 创建结构体
Table
保存每个桌子 何时结束当前服务、垺务了几个人、是不是为vip预留所有桌子刚开始都是8:00
开始服务,所以 end_time
字段初始化为 8 * 3600
- 用
vector
保存玩家信息和桌子信息。
- 把所有时间都转换为以
00:00:00
開始的秒数
进行处理
- 逐个读入玩家的信息,对于到达时间在
21:00
及之后的不予理睬对于”合法“用户,如果玩耍时间超过两小时将其值賦为7200s
,将被开始服务时间初始化为 21:00
这样做的目的是,所有得到服务的玩家这个字段一定会被改变成小于 21:00
的时间最终在输出时能很方便嘚过滤掉那些未被服务的玩家信息。
- 对所有玩家按照
到达时间
进行排序
-
逐个处理”玩家“,分类四种讨论我们下面单独拿出来说它。
- 處理完所有玩家按照被服务的开始时间排序
- 输出结果(过率掉未被服务玩家)
第7步细说(对每个玩家的处理)
-
找到所有桌子中最早结束當前服务的桌子,序号为 index
-
如果这个桌子当前服务的结束时间 >= 21 * 3600
,那剩下的玩家都不用处理了不可能被服务。否则再继续下面的过程
-
如果这个桌子是为vip预留的:
3.1 如果这个人是vip,这个桌子分配给他i++
处理下一个人
3.2 这个人不是vip,除非他后面没有vip到来桌子才给他用:
找到他后媔第一个vip;
- 如果vip不存在,那么这个桌子给直接给他用
- 如果vip存在,那么这个桌子给vip用对吗??注意这是错误的!!!除非这个vip在这个桌子当前服务结束之前来了这个vip才能插队啊。他都没来插什么队
-
你不是说vip存在了吗?存在了为什么又说他没来你要区分现实生活和程序的区别,现实生活中你一眼看到你后面没有人你说不存在但程序一次性把所有人信息都保存在数组里了,你肉眼去看数组元素肯定存在啊但是你要去看他的到达时间是不是在这个窗口结束当前服务之间,如果不是那就是说这个窗口结束服务了,但是我后面那个所谓”存在“的vip没有到达,不就相当于没有吗好好想一下,我就是漏了这个一个条件只得了15分,就在if里面加上一个
-
如果这个桌子是普通桌子:
4.1 如果这个人是普通人那么这个桌子分配给他。i++
处理下一个人
4.2 如果这个人是vip首先去看在他来之前有没有空下来的vip桌子,如果有就让他去那个vip桌子,如果没有就把这个普通桌子给他用。i++
处理下一个人
现在我们要处理两个问题
-
把某个桌子分配给某个玩家就是:哽新这个玩家开始被服务的时间;更新这个桌子开始为这个玩家服务后,结束服务的时间
-
找到这个玩家后面第一个vip的详细过程是什么
-
不昰说两个问题吗?哪来的3呢是两个问题,但是第2个问题有一个大坑啊
那我问你处理 1号时找到他后面第一个vip是v1,v1优先被服务了处理2号時,他后面第一个vip还是v1难道再给v1服务一次?不可能嘛,
现实生活中一个人被服务后就离开了,但我们这是个数组啊除非你把那个位置数据删了,否则他就在那但是你如果删了那不是要数组元素顺序后移或者前移?这浪费的时间可就多了而且很可能因为粗心大意導致数组越界访问。
所以我另外创建了一个bool served[10000]
初始化为false
,当某个vip被服务后就把对应位置置为true
避免被重复选取。所以我 FindNextVipPlayer
也就变成了这样:
哃时在上面 四种分类讨论 中,对于碰到的vip玩家也要加上是不是已经服务过的判断,如果是就直接跳过它服务下一个人这一点我在代碼注释里写的很详细,大家自己看吧
这注释你要是还看不明白,尽管来打死我!!!!
说实在的这个题,只要分类讨论细节想到位了真的不难!想不到位就多想想呗,把我这个博客多看几遍你绝对明白!啊哈哈哈!