7

我正在解决以下问题并采用蛮力方法，但无法提出一个好的解决方案。问题如下：

有2*N张卡。您和您的对手将它们分开（给您 N 张牌，给他们 N 张牌）。您确切地知道他们有什么牌以及他们将按什么顺序打牌。

游戏规则如下：在前 N/2 轮中，拥有最高牌的人获胜，在最后 N/2 轮中，拥有最低牌的人获胜。

鉴于这些规则和你的对手在那里打牌的顺序，你可以获得的最大胜利数量是多少。

例子：

你有牌：2、5、6、7。你的对手有牌：1、8、4、3，并按顺序打出。

你可以得到的最高分是 2，因为你打 7 对 1，输掉第 2 和第 3 轮，然后在最后一轮打 2 赢。

我的想法：把你的牌分成两堆，你的大号和小号。然后找出最佳匹配。

伪代码/算法的想法将不胜感激。

编辑：总共有 N 轮。前 N/2 轮：较高的牌获胜。最后 N/2 轮：较低的牌获胜。N 必须是偶数。

4

2 回答 2

2

我建议：

  • 将您的卡片分成更大/更低的 2 堆
  • 对它们进行排序
  • 按价值对对手更大的牌进行排序（第一轮）
  • 从最大到较低的对手牌：
    如果您剩余的最大牌低于对手牌，则打最低牌（输）
    ，否则打您的最高牌（赢）

下桩类似，倒序。

于 2015-12-14T00:37:46.463 回答
1

首先，创建一个包含 N 个项目的数组（每轮一个）。每个项目都是该轮“获胜牌”的列表，即您将赢得该轮的牌组。在你的例子中，你会得到{{2567},{},{2},{2}}.

下面的列表给出了一张牌应该被“分配”到一轮的一些情况。这意味着我们决定在那轮打出那张牌，之后任何事情都无法改变。分配牌后，算法应在从轮组中删除指定轮次并从获胜牌组中删除指定轮次后继续进行。

很明显，在任何情况下应用这些规则中的任何一个都不会减少可能获胜的数量，因此在开始蛮力之前尽可能多地应用它们总是一个好主意。

  • 如果卡 C 可以赢得 R 轮，而卡 C 不能赢得另一轮，则将卡 C 分配给 R 轮。
  • 如果卡片 C 不能在任何回合中获胜，并且回合 R 不能被任何卡片获胜，则将卡片 C 分配给回合 R。
  • 如果卡 C 可以在前 N/2 轮中的某些轮中获胜，但卡 C 在最后 N/2 轮中的任何轮中都无法获胜，并且卡 C 是具有此属性的卡中最高的，则将卡 C 分配给它获胜的最困难的一轮（即C 获胜的对手牌中最高的牌）。
  • 如果卡 C 可以在最后 N/2 轮中的某些轮中获胜，但卡 C 在前 N/2 轮中的任何轮中都无法获胜，并且卡 C 是具有此属性的卡中最低的，则将卡 C 分配给它获胜的最困难的一轮（即C牌获胜的对手的最低牌）。

请注意，将一张牌分配给一个回合会同时改变回合和在每一回合中获胜的牌，因此即使这些规则中的一个不适用，在应用其他规则后它也可能变得适用。因此，必须反复尝试它们，直到对它们进行完整的迭代，不会产生新的分配。

这不是一个确定的解决方案，但它肯定会让最后的暴力破解步骤变得更容易。

于 2015-12-14T00:56:17.777 回答