射箭比赛中的最大得分

标签: 位运算 数组 回溯 枚举

难度: Medium

Alice 和 Bob 是一场射箭比赛中的对手。比赛规则如下：

  1. Alice 先射 numArrows 支箭，然后 Bob 也射 numArrows 支箭。
  2. 分数按下述规则计算：
    1. 箭靶有若干整数计分区域，范围从 0 到 11 （含 0 和 11）。
    2. 箭靶上每个区域都对应一个得分 k（范围是 0 到 11），Alice 和 Bob 分别在得分 k 区域射中 ak 和 bk 支箭。如果 ak >= bk ，那么 Alice 得 k 分。如果 ak < bk ，则 Bob 得 k 分
    3. 如果 ak == bk == 0 ，那么无人得到 k 分。

  • 例如，Alice 和 Bob 都向计分为 11 的区域射 2 支箭，那么 Alice 得 11 分。如果 Alice 向计分为 11 的区域射 0 支箭，但 Bob 向同一个区域射 2 支箭，那么 Bob 得 11 分。

给你整数 numArrows 和一个长度为 12 的整数数组 aliceArrows ，该数组表示 Alice 射中 0 到 11 每个计分区域的箭数量。现在，Bob 想要尽可能 最大化 他所能获得的总分。

返回数组 bobArrows ，该数组表示 Bob 射中 0 到 11 每个 计分区域的箭数量。且 bobArrows 的总和应当等于 numArrows 。

如果存在多种方法都可以使 Bob 获得最大总分，返回其中 任意一种 即可。

示例 1：

输入：numArrows = 9, aliceArrows = [1,1,0,1,0,0,2,1,0,1,2,0]
输出：[0,0,0,0,1,1,0,0,1,2,3,1]
解释：上表显示了比赛得分情况。
Bob 获得总分 4 + 5 + 8 + 9 + 10 + 11 = 47 。
可以证明 Bob 无法获得比 47 更高的分数。

示例 2：

输入：numArrows = 3, aliceArrows = [0,0,1,0,0,0,0,0,0,0,0,2]
输出：[0,0,0,0,0,0,0,0,1,1,1,0]
解释：上表显示了比赛得分情况。
Bob 获得总分 8 + 9 + 10 = 27 。
可以证明 Bob 无法获得比 27 更高的分数。

提示：

  • 1 <= numArrows <= 105
  • aliceArrows.length == bobArrows.length == 12
  • 0 <= aliceArrows[i], bobArrows[i] <= numArrows
  • sum(aliceArrows[i]) == numArrows

Submission

运行时间: 36 ms

内存: 16.2 MB

class Solution:
    def maximumBobPoints(self, numArrows: int, aliceArrows: List[int]) -> List[int]:
        ans = []
        path = []
        max_sum = 0
        def dfs(i, k, s):  # 从高遍历到低
            nonlocal ans, max_sum
            if (i + 1) * i // 2 + s <= max_sum:  # 若接下来都得分的得分总和还是小于max_sum（剪枝）
                return
            if i == 0: 
                path.append(k)
                max_sum = s
                ans = path[::-1]
                path.pop()
                return

            if k > aliceArrows[i]:  # 箭够，选
                path.append(aliceArrows[i] + 1)
                dfs(i - 1, k - aliceArrows[i] - 1, s + i)
                path.pop()
            path.append(0)  # 不选
            dfs(i - 1, k, s)
            path.pop()

        dfs(11, numArrows, 0)
        return ans

Explain

这道题解采用了深度优先搜索(DFS)的方法，从高分到低分区域进行遍历。我们试图确定Bob在每个得分区间应该射出多少箭以最大化他的总分。如果Bob想在某个得分k的区域获得分数，他必须射出的箭数要比Alice多至少一箭。因此，我们首先检查Bob是否有足够的箭来在这个区域得分（即箭数要大于Alice在该区域的箭数），然后决定是否投入箭数超过Alice，以抢夺这个得分区域。这种方法使用了剪枝技术，当确定接下来即使所有区域都得分，总得分还是无法超过当前已知的最大得分时，就停止进一步搜索。

时间复杂度: O(2^12)

空间复杂度: O(12)

class Solution:
    def maximumBobPoints(self, numArrows: int, aliceArrows: List[int]) -> List[int]:
        ans = []  # 最优解的箭数分配
        path = []  # 当前尝试的箭数分配
        max_sum = 0  # 目前已知的最大得分
        def dfs(i, k, s):  # 从得分高的区域开始递归探索
            nonlocal ans, max_sum
            if (i + 1) * i // 2 + s <= max_sum:  # 剪枝，如果即使剩余区域都得分也无法超过最大得分
                return
            if i == 0:  # 达到最低分区域，更新最大得分和答案
                path.append(k)
                max_sum = s
                ans = path[::-1]  # 因为是反向填充的，所以需要反转结果
                path.pop()
                return
            if k > aliceArrows[i]:  # 箭够，尝试抢分
                path.append(aliceArrows[i] + 1)
                dfs(i - 1, k - aliceArrows[i] - 1, s + i)
                path.pop()
            path.append(0)  # 不尝试抢这个分
            dfs(i - 1, k, s)
            path.pop()
        dfs(11, numArrows, 0)
        return ans

Explore

这个剪枝策略是基于一个数学公式的，`(i + 1) * i // 2`是计算从1加到i的和，即1到i的自然数和。在这个题解中，这个公式被用来估计从当前得分区域i开始到最高得分区域的所有可能的最大得分。如果将当前已获得的分数s与可能的最大得分相加，即`(i + 1) * i // 2 + s`，若这个值小于或等于已知的最大得分`max_sum`，则意味着即使在剩下的所有区域Bob都拿到最高分，其总得分也无法超过当前已知的最大得分，因此继续探索这个路径是无效的。这种策略有效地减少了搜索空间，提高了算法的效率。

从得分高的区域向低得分区域递归的策略有两个主要优势。首先，它允许算法优先探索高值得分的可能性，这有助于尽早发现高得分的解决方案，从而提早更新最大得分`max_sum`，增强剪枝效果，减少不必要的计算。其次，这种策略有助于更快地到达剪枝条件，因为高分区域的失败（即无法超过Alice获取分数）会迅速排除许多不可能的路径，从而优化整个搜索过程。

在DFS的实现中，为了方便从得分高的区域向低得分区域递归，`path`数组是从后往前填充的，即先记录高分区的尝试结果，最后记录低分区的结果。因此，当递归完成并找到一个有效的解决方案时，`path`数组中得分的顺序实际上是从高到低。为了使得分的顺序与题目要求的从低到高一致，需要在最终使用结果前将`path`数组进行反转，确保输出格式正确，符合题目的箭数分配顺序要求。