Facebook 的很多人都喜欢玩星际争霸 II™。他们中的一些人使用星际争霸 II™ map 编辑器制作了自定义游戏。在这款游戏中，您将扮演高贵的 Protoss，保卫您的家乡 Shakuras，抵御庞大的 Zerg 军队。在被淹没之前，您必须对 Zerg 造成尽可能多的伤害。您只能 build 两种类型的单位，护盾发生器和战士。护盾发生器不会造成伤害，但你的军队每 build 一个护盾发生器就能存活一秒。战士每秒造成一次伤害。在你的护盾发生器失效后，你的军队会立即被淹没。在你的军队被占领之前，你应该 build 多少护盾发生器和多少战士来对 Zerg 造成最大的伤害？因为 Protoss 重视勇敢，如果有多个解决方案，您应该返回使用最多战士的那个。
约束
- 1 ≤ G(一个护盾发生器的成本)≤ 100
- 1 ≤ W(一名战士的成本)≤ 100
- G + W ≤ M(可用资金)≤ 1000000000000 (1012)
最佳答案
这是一个复杂度为 O(W) 的解决方案。令g 为我们构建的发电机数量，同样令w 为我们构建的勇士数量(G, W 为相应的每单位价格)。
我们注意到我们想要最大化 w*g 服从 w*W + g*G <= M。
首先，我们将去掉其中一个变量。请注意，如果我们为 g 选择一个值，那么显然我们应该用剩余的金额 M - g*G 购买尽可能多的战士。换句话说，w = floor((M-g*G)/W)。
现在，问题是根据 0 <= g <= floor(M/G) 最大化 g*floor((M-g*G)/W) .我们想去掉地板，所以让我们考虑 W 个不同的情况。让我们写成 g = W*k + r，其中 0 <= r < W 是 g 除以 W< 的余数/b>.
现在的想法是修复r，并插入g的表达式，然后让k成为方程中的变量。我们将在 k 中得到以下二次方程:
设p = floor((M - r*G)/W)，则方程为(-GW) * k^2 + (Wp - rG)k + rp .
这是一个二次方程，当 x 趋于无穷大或负无穷大时趋于负无穷大，因此它在 k = -B/(2A) 处具有全局最大值。为了找到k的合法值的最大值，我们将尝试k的最小合法值，k的最大合法值和实际最大值的两个最近的整数点，如果它们在合法范围内。
r 的所有值的总体最大值是我们正在寻找的值。由于 r 有 W 个值，并且需要 O(1) 来计算固定值的最大值，因此总时间为 < b>O(W).
关于algorithm - Facebook 黑客杯 : Power Overwhelming，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/4701154/