Lines | Bugs | Time |
---|---|---|
237 | 10+ | 16h |
不想赘言。
此次的电梯作业在还没开始写时,笔者想了一些方案,到了在写的时候基本都否认掉了,可以说写的版本已经是笔者推翻了自己之前显然不够好的没有付诸实践的版本的更新。此外,笔者发现这次的代码作业并不好写,除了一些细节的地方,还有就是没有AC的结果,以至于去深究整个请求,越想越繁复,没有想到什么可以一步到位的考量,很是头大。
从笔者的理解来看,笔者写了一部很朴素(在笔者策略上的朴素)并且异常电梯。(异常即指即如果请求时刻远大于处理完其时刻之前的所有请求的结束时刻,电梯可在该极大请求时刻便到达该乘客所在楼层进行接送)
笔者之前的方案以及代码考量的是如何对请求进行选择达到最小的等待总和,如有:
1、每次只接送一名乘客,到达目的地后再去接下一位(太过朴素,等待时间总和不可能最小)
2、不断进行对当前时间(nowtime)进行模拟(nowtime++),然后扫一遍请求,不断重复上述过程进行编码(时间复杂度过高,虽然没有限制时间,但是也希望能尽量节约时间)
3、根据当前电梯去向与乘客所在楼层的差值,以及搭载同层等待乘客或是顺路乘客(优,但是苦于不知道如何理清头绪,后续会加入实现)
下面将叙述提交版本:
笔者代码首先将输入根据请求时刻(asktime)以及(乘客所在楼层与目的楼层的差值:value)进行排序(asktime为第一关键字),也特判了一些特殊情况(详情见代码注释),而对于不能特判的一般情况,笔者采用的策略是——在排序完,优先接送value小的乘客(显然有许多反例证明此策略不能达到乘客最小时间等待总和),对于输出,笔者只进行目的地(即中间的停靠不输出)和等待时间的输出。
笔者此次的代码虽然编写了很久,但是并没有达到笔者的预期效果,笔者仍在此期间不断修改(昨晚(2018.2.10)得知寒假后续作业均是电梯,有点头大,但是也很庆幸,这样就会真的会去做后续的改进),此次的提交是笔者这几天(2018.2.7~2018.2.11)中的最新版本,但是显然不是最后的版本,笔者也深知其中很多的错误。笔者后续打算添加电梯的运行方向以达到更优的结果(如能接送恰好连续的同一楼层的乘客,以及某几个顺路的乘客等等,当然这些都是在不影响最后最优时间的情况下去做的),以及希望能够把这部电梯当前的朴素编写成成高端点的朴素,直到最后实现正常的电梯版本。
样例有上文中提及的特殊情况(如在当前乘客进入电梯时,恰好出现了下一请求(时间连续)等等),已经已经到达目的层的奇葩请求,其实就是很水的样例实话说是高端点的版本写不出来,只好先写成这样,代码冗长,实现功能简单,简直菜得可怕
Sample1~5
PTA screenshot