Merge Slimes 题解

· · 题解

题意：N 种史莱姆，第 i 种大小为 S_i，有 C_i 个。2 个大小为 X 的史莱姆可以合成一个大小为 2X 的史莱姆，问在若干次合并之后最少可以剩下多少史莱姆。

思路就是循环取最小的史莱姆，因为小的史莱姆只能合成大的史莱姆，所以就不会出现后面的还可以和前面的合并的情况。

取出当前最小史莱姆合并，如果当前大小的数量是奇数就答案加上 1，然后将大小乘上 2 的史莱姆个数加上当前史莱姆个数除以 2。

这道题有在实现的方式上比较有趣，这里会给出 3 种实现。

  1. set + map 版

使用 set 记录当前所有的史莱姆大小，然后用 map 将大小和数量连起来（当时脑子抽了没想到 map 可以按键值排序还傻逼地用 set 排一遍）。

每一次从头取 set 中的元素，然后用 map 获取当前大小史莱姆的数量，将合成后的史莱姆大小加入 set，数量加入 map（注意要用 +=，不要直接赋值）。

这个东西实现不好会超时一点，set 在删除最前面的元素时要删指针不要删数。

code

  1. set 版

用结构体存储大小和数量，重载运算符按大小排序。

每一次从头取出大小和数量，操作后查找 set 中有没有 2 倍当前大小的元素，有的话取出，加上合成的过后再放回。

code

  1. map 版

将 set+map 版改成只有 map，由于 map 自动按键值从小到大排序，所以可以代替 set 的操作。

code

还有一种思路，就是把大的史莱姆往小了砍，砍成大小为奇数后就加进一个集合里面，最后统计就可以了。