2022 百度之星初赛第一场

发布时间 2023-08-10 18:14:21作者: 次林梦叶

写在前面:  

  非正式题解,题解在QQ官群有(虽然没有代码)

 

小度养小猫

   

   首先对ci按照大小排个序,然后再时间允许的情况下越早越好

    这个倒是想到了,但是有一个问题:我们如何快速找到对应的猫应该喂养的时间?

  如果时间没有冲突还好说,直接按照分配即可

 

  但是如果时间有冲突了,同时可能有些时间已经被分配走了,如果一个一个遍历适合的时间的话就会超时   

 

    有个特别好的想法就是:

    我们开个堆,以ci大小排序

    将前k+1个猫装到堆中,然后让堆顶的猫用目前最早的时间

    然后pop这个猫,装下一个猫

    这个做法的正确性是比如最开始,即使k+1个猫之后的猫c十分大,因为时间冲突的原因也用不了最早的时间

    堆中装的都是最早时间不冲突的猫

 

 

大水题

  

     确实是个水题

   但是注意这里可以多个bfs开始点放到同一个queue中进行bfs

    如果是分开,单独放到一个queue中分别bfs会出超时