我们有 N 个类型 1 的硬币和 M 个类型 2 的硬币。游戏板有 N 个类型 1 的方格和 M 个类型 2 的方格。在这个游戏中,我们必须在每个方格中放入一枚硬币。放置完所有硬币后,我们将根据我们的硬币放置策略获得分数。
如果 1 型方 block 包含 1 型硬币,那么我们将获得 A 点,如果 2 型方 block 包含 2 型硬币,那么我们将获得 B 点,在所有其他情况下,我们将获得 C 点。我们的游戏总得分将是所有方格得分的总和。
可用的用户输入有(N、M、A、B、C)
我们怎样才能最大化我们的分数?
例如,如果 N=3 M=4 A=500 B=800 C=600
采用最优策略,我们将 3 个类型 1 的硬币放入 3 个类型 1 的方格中,得到分数 = 500+500+500 = 1500,我们将 4 个类型 2 的硬币放入 4 个类型 2 的方格中,得到分数分数 =800+800+800+800 = 3200 因此总分将为 1500+3200 = 4700
最佳答案
这很简单。一种显然有效的解决方案是将所有 1 类硬币放置在 1 类方 block 中。这会给你一定的分数。我们现在可以将任何 1 类硬币与 2 类硬币交换。这样做,我们将失去 A + B
的分数,但获得 2 C
的分数。因此,只有 2 C > A + B
时交换才有意义。我们可以交换 min(N, M)
次。所以最高分是:
nSwaps =
if 2 * C > A + B then
min(N, M)
else
0
end if
maxScore = N * A + M * B + nSwaps * (2 * C - A - B)
关于c - 这个简单游戏的高效算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/31635246/