卡算法游戏

2018-06-10 12:09:53

我正在玩下面的问题，并采取暴力手段，但不能提出一个很好的解决方案。问题如下：

有2 * N卡。你和你的对手将他们分开（N卡给你，N给他们）。你确切地知道他们有什么牌和他们将以什么顺序进行比赛。

游戏规则如下：对于最初的N / 2轮，拥有最高牌的人获胜，而对于最近的N / 2轮，拥有最低牌的人获胜。

根据这些规则以及对手玩牌的顺序，您可以获得的最高胜率是多少。

例：

你有牌：2,5,6,7。你的对手拥有牌：1，8，4，3，并按顺序进行。

你可以得到的最高分数是2，因为你打了7分给他们1，输掉第二轮和第三轮，然后在上一轮打2赢。

我的想法：将你的卡分成两堆，你的大号和低号。然后找出最佳匹配。

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

编辑：共有N轮。第一轮N / 2回合：更高的牌赢。最近的N / 2轮：较低的牌获胜。 N必须均匀。

我建议：

将你的卡分成两堆/更低

整理它们

按价值排序对手的更多牌（第一轮）

从大到小对手卡：
如果您的剩余最大值低于对手卡，则玩最低卡（丢失）
别玩你最高的牌（赢）

类似于较低的堆，反转顺序。

首先，创建一个包含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获胜的对手牌中最低的一张）。

请注意，将一张牌分配给一轮会改变每轮中获胜的回合和牌，因此即使其中一个规则不适用，也可以在应用其他规则后适用。所以他们必须迭代尝试，直到完全迭代所有这些都不会产生新的分配为止。

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

链接地址: http://www.djcxy.com/p/31067.html