tkdsheep-solution-0029

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

宠物小精灵，宠物数量为n，精灵球的容量为m，给出宠物作战的顺序，要求最少的pick数，pick即指当一个宠物上场时，如果它不在精灵球内，则需要pick
作战完后可以选择把宠物放入精灵球或者不放，精灵球里的宠物也可以随时扔出去腾出空间给新的宠物

用上各种logn级别的数据结构即可，可以使用STL里面的map和priority_queue

首先用一个map维护，得到第i个上场的宠物，下一次上场是什么时候，即i的映射为next[i]

然后从第一个上场的宠物开始做，维护一个新的map和priority_queue，里面存的是当前在精灵球里的宠物

对于一个新的宠物i，如果它在map里（在精灵球里），那么更新这个宠物下一次上场的时间

如果它不在map里

那么就看精灵球的size是否还可以加新的宠物，可以就直接加

不可以就查看精灵球内下一次出场最晚的宠物，如果时间比这个新的宠物晚，则对他们做调换

宠物小精灵，宠物数量为n，精灵球的容量为m，给出宠物作战的顺序，要求最少的pick数，pick即指当一个宠物上场时，如果它不在精灵球内，则需要pick

作战完后可以选择把宠物放入精灵球或者不放，精灵球里的宠物也可以随时扔出去腾出空间给新的宠物

用上各种logn级别的数据结构即可，可以使用STL里面的map和priority_queue

首先用一个map维护，得到第i个上场的宠物，下一次上场是什么时候，即i的映射为next[i]

然后从第一个上场的宠物开始做，维护一个新的map和priority_queue，里面存的是当前在精灵球里的宠物

对于一个新的宠物i，如果它在map里（在精灵球里），那么更新这个宠物下一次上场的时间

如果它不在map里

那么就看精灵球的size是否还可以加新的宠物，可以就直接加

不可以就查看精灵球内下一次出场最晚的宠物，如果时间比这个新的宠物晚，则对他们做调换