0

我在 Google Code Jam 中阅读了这个优化问题。（比赛已经结束了，可以聊聊了。）

Armin 正在玩由 Hemisphere Games 开发的基于物理的益智游戏 Osmos。在这个游戏中，他扮演一个“微粒”，四处移动并吸收更小的微粒。

英文中的“mote”是一个小颗粒。在这个游戏中，它是一个吸收（或被吸收）其他东西的东西！本题中的游戏与 Osmos 有类似的想法，但并不假设你已经玩过这款游戏。

当 Armin 的尘埃吸收了一个较小的尘埃时，他的尘埃会随着较小尘埃的大小而变大。现在它更大了，它可能能够吸收更多的微粒。例如：假设 Armin 的 mote 大小为 10，还有其他大小为 9、13 和 19 的 mote。一开始，Armin 的 mote 只能吸收大小为 9 的 mote。当它吸收时，它的大小为 19。然后它只能吸收大小为 13 的微粒。当它吸收时，它将具有大小 32。现在阿明的微粒可以吸收最后一个微粒。

请注意，Armin 的微粒可以吸收另一个微粒当且仅当另一个微粒更小。如果另一个尘埃与他的大小相同，他的尘埃就无法吸收它。

您负责为 Armin 创建微尘以吸收的程序。该程序已经创建了一些大小不一的mote，并创建了Armin 的mote。不幸的是，考虑到他的微尘的大小和其他微尘的列表，Armin 的微尘可能无法将它们全部吸收。

你想解决这个问题。您可以按任意顺序、任意次数执行两种操作：您可以将任意正整数大小的微尘添加到游戏中，或者您可以移除任何一个现有微尘。为了使 Armin 的微粒能够吸收所有其他微粒，您可以执行这些操作的最少次数是多少？

例如，假设 Armin 的 mote 大小为 10，而其他 mote 的大小为 [9, 20, 25, 100]。此游戏目前无法解决，但通过添加大小为 3 的微尘并移除大小为 100 的微尘，您只需 2 次操作即可解决此问题。这里的答案是2。

如何解决？（请用散文解释，而不是神秘代码）

我认为“给定一个可行的解决方案，删除一个尺寸为 x 并添加一个更大的尺寸为 y，有一个更好的（至少同样好）可行的解决方案，其中所有添加的节点都小于所有删除的节点”（而不是删除mote size x，在较大的mote size y之后吃掉它）

这提出了一种快速算法。将微粒从小到大排序。吃。如果卡住，记录“删除其余部分”作为潜在的解决方案。添加尘埃大小player - 1，直到大到可以吃掉我们粘在上面的尘埃。重复。记录最终的“仅添加”解决方案。从记录的那些中选择最优解。

我在 Python 中实现了这个算法。我相当确定我的代码正确地实现了我的算法。我猜我的算法错了？

4

2 回答 2

2

我认为您的问题出在代码中：

# Let's add motes until we can eat it.
while A <= m:
  A += A-1
  operations += 1

这模拟了添加更多的微粒，直到你大到可以吃掉当前的微粒，但你不吃它。

换句话说，我认为您需要将其更改为：

while A <= m:
  A += A-1
  operations += 1
A+=m

当你吃当前的食物时，以反映成长。

于 2013-05-07T13:04:58.783 回答
0

将微粒从小到大排序。吃。如果卡住了，请添加一个额外的大小currentMoteSize - 1，直到大到可以吃掉我们卡住的微尘。如果添加的 extraMotes 的数量 >= 剩余的 mote的数量，则返回到目前为止计数的操作数 + 剩余模式的数量，否则如果添加的 extraMotes 的数量 >= 的 mote 总数，则返回总数number of motes，否则吃掉当前的 mote，将额外的 mote 数量添加到到目前为止计算的操作数中。重复直到我们吃完所有的微粒。返回计数的操作数。

于 2013-05-07T13:20:56.980 回答