0

你玩一个新的集换式卡牌游戏。你和电脑各有一张卡片组。电脑打牌，然后你打牌。每张牌都有一个力量值，力量值较高的牌获胜。如果你和如果电脑有同样强的牌，电脑就赢了。你知道电脑的卡片。您的目标是计算您赢得的最大化卡的强度值的总和。为此，您将获得两个整数数组，它们分别代表您的卡片和计算机的卡片。

你会得到卡片 [5, 15, 100, 1, 5]。计算机使用相同的卡片，[5, 15, 100, 1, 5] 也是如此。当计算机放置 100 时，您放置 Your 1，因为您无法获胜。如果他打出 15，你打出 100 就赢了。如果他打出 5，那么打出你的 15。如果他打出第二个 5，那么打出你的 5 并输掉这一轮。如果他投出他的 1，你用你的第 5 个总数反击。您将获得价值 120 的获胜卡。

任务：描述你可以计算总和的贪心算法思想。在此处输入图像描述

我的算法：当计算机从它的牌堆中放置最大的牌（在本例中为 100）时，我将最小的数字放在我的情况下 1。我会继续这样做，并且每当我赢时我都会写添加结果

有人对贪心算法有其他建议吗

4

1 回答 1

2

你的想法是正确的。这里还有一点需要考虑。

对于 [5, 15, 100, 1, 5]，

  1. 计算机抛出 5，而你抛出 100，因为它是最大的。
  2. 下一台电脑掷出 15，现在你的最大值是 15，你将失去这一点。

为避免这种情况，您应该选择给定数字的下一个最大值。

  1. 当计算机抛出 5 时，你抛出 15。
  2. 当计算机掷出 15 时，您掷出 100 即可获得分数。

如果所有卡片都是唯一的，您可以通过这种方式赢得 (n-1) 点，其中 n 是数组的大小。

因此，算法将是找到下一个最大值。如果可以找到它，则返回它，否则返回数组中的最小数字。

于 2020-11-30T17:46:14.750 回答