【题目描述】有 n 个人在排队取餐。每个人都有自己的口味偏好他们会在手机上自助选择好自己想要的餐品。不同的餐品需要不同的制作时间。你是这家餐厅的老板作为生意火爆的网红打卡点你的餐厅营业时间一天只有m分钟。如果某个顾客能够吃到他点的餐品他会就给餐厅打分。第i个人如果吃到了餐品他就会给餐厅打xi分。但是由于不能马上吃到餐品顾客就会产生不满。如果第i个人吃到餐品等待了q分钟他就会减少打分分数就会减少q∗
感觉题目有点长啊,其实就是一个贪心+优先队列的问题。
第一步,我们将所有的点按照完成所需要的时间排序,这是显然的,时间短的先完成肯定更好。
第二步,我们需要维护一个优先队列,这个优先队列的作用就是存储等待的顾客。我们将等待时间最短的顾客放到队首,然后我们每次完成一个订单的时候,就将队首的顾客弹出,如果这个顾客等待的时间超过了他的等待周期,那么我们就将他的分数降低30分,然后将他重新加入队列中。
第三步,我们需要维护一个总分数,当然这个总分数不是最终结果,因为我们还需要考虑顾客等待的问题。每次完成一个订单的时候,我们需要将这个顾客的分数加入总分数中,如果顾客等待的时间超过了他的等待周期,那么我们就需要将分数减少30分。
最后,我们就可以得到最终的结果了。
原文地址: http://www.cveoy.top/t/topic/8ty 著作权归作者所有。请勿转载和采集!