Medium

题目描述

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

  • Alice 先射 numArrows 支箭，然后 Bob 射 numArrows 支箭。
  • 得分计算方式如下：
    • 靶子有从 0 到 11 的整数得分区域。
    • 对于得分为 k（0 到 11 之间）的每个区域，假设 Alice 和 Bob 分别在该区域射了 ak 和 bk 支箭。如果 ak >= bk，那么 Alice 得到 k 分。如果 ak < bk，那么 Bob 得到 k 分。
    • 但是，如果 ak == bk == 0，那么没有人得到 k 分。

例如，如果 Alice 和 Bob 都在得分为 11 的区域射了 2 支箭，那么 Alice 得到 11 分。另一方面，如果 Alice 在得分为 11 的区域射了 0 支箭，而 Bob 在同一区域射了 2 支箭，那么 Bob 得到 11 分。

给定整数 numArrows 和大小为 12 的整数数组 aliceArrows，其中 aliceArrows[i] 表示 Alice 在得分为 i 的区域射的箭数。现在，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 <= 10^5
  • aliceArrows.length == bobArrows.length == 12
  • 0 <= aliceArrows[i], bobArrows[i] <= numArrows
  • sum(aliceArrows[i]) == numArrows

解题思路

这是一个典型的枚举问题。由于只有12个得分区域，我们可以使用位运算枚举所有可能的获胜组合。

核心思路：

  1. 对于每个得分区域 i，Bob要想获得该区域的分数，他必须射比Alice更多的箭，即至少射 aliceArrows[i] + 1 支箭
  2. 由于总共只有12个区域，我们可以使用12位的二进制数来表示Bob选择获胜的区域组合
  3. 对于每个组合，计算需要的总箭数和能获得的总分数
  4. 如果箭数不超过限制，更新最优解

算法步骤：

  1. 枚举所有可能的获胜组合（0到2^12-1）
  2. 对于每个组合，计算Bob需要的箭数和能获得的分数
  3. 如果箭数合法且分数更高，更新最优解
  4. 将剩余的箭全部分配给得分为0的区域

时间复杂度为O(2^12) = O(4096)，完全可以接受。

代码实现

class Solution {
public:
    vector<int> maximumBobPoints(int numArrows, vector<int>& aliceArrows) {
        int maxScore = 0;
        int bestMask = 0;
        
        // 枚举所有可能的获胜组合
        for (int mask = 0; mask < (1 << 12); mask++) {
            int arrowsNeeded = 0;
            int score = 0;
            
            for (int i = 0; i < 12; i++) {
                if (mask & (1 << i)) {
                    arrowsNeeded += aliceArrows[i] + 1;
                    score += i;
                }
            }
            
            if (arrowsNeeded <= numArrows && score > maxScore) {
                maxScore = score;
                bestMask = mask;
            }
        }
        
        vector<int> bobArrows(12, 0);
        int remainingArrows = numArrows;
        
        for (int i = 0; i < 12; i++) {
            if (bestMask & (1 << i)) {
                bobArrows[i] = aliceArrows[i] + 1;
                remainingArrows -= bobArrows[i];
            }
        }
        
        // 将剩余的箭分配给得分为0的区域
        bobArrows[0] += remainingArrows;
        
        return bobArrows;
    }
};

class Solution:
    def maximumBobPoints(self, numArrows: int, aliceArrows: List[int]) -> List[int]:
        max_score = 0
        best_mask = 0
        
        # 枚举所有可能的获胜组合
        for mask in range(1 << 12):
            arrows_needed = 0
            score = 0
            
            for i in range(12):
                if mask & (1 << i):
                    arrows_needed += aliceArrows[i] + 1
                    score += i
            
            if arrows_needed <= numArrows and score > max_score:
                max_score = score
                best_mask = mask
        
        bob_arrows = [0] * 12
        remaining_arrows = numArrows
        
        for i in range(12):
            if best_mask & (1 << i):
                bob_arrows[i] = aliceArrows[i] + 1
                remaining_arrows -= bob_arrows[i]
        
        # 将剩余的箭分配给得分为0的区域
        bob_arrows[0] += remaining_arrows
        
        return bob_arrows

public class Solution {
    public int[] MaximumBobPoints(int numArrows, int[] aliceArrows) {
        int maxScore = 0;
        int bestMask = 0;
        
        // 枚举所有可能的获胜组合
        for (int mask = 0; mask < (1 << 12); mask++) {
            int arrowsNeeded = 0;
            int score = 0;
            
            for (int i = 0; i < 12; i++) {
                if ((mask & (1 << i)) != 0) {
                    arrowsNeeded += aliceArrows[i] + 1;
                    score += i;
                }
            }
            
            if (arrowsNeeded <= numArrows && score > maxScore) {
                maxScore = score;
                bestMask = mask;
            }
        }
        
        int[] bobArrows = new int[12];
        int remainingArrows = numArrows;
        
        for (int i = 0; i < 12; i++) {
            if ((bestMask & (1 << i)) != 0) {
                bobArrows[i] = aliceArrows[i] + 1;
                remainingArrows -= bobArrows[i];
            }
        }
        
        // 将剩余的箭分配给得分为0的区域
        bobArrows[0] += remainingArrows;
        
        return bobArrows;
    }
}

var maximumBobPoints = function(numArrows, aliceArrows) {
    let maxScore = 0;
    let bestMask = 0;
    
    // 枚举所有可能的获胜组合
    for (let mask = 0; mask < (1 << 12); mask++) {
        let arrowsNeeded = 0;
        let score = 0;
        
        for (let i = 0; i < 12; i++) {
            if (mask & (1 << i)) {
                arrowsNeeded += aliceArrows[i] + 1;
                score += i;
            }
        }
        
        if (arrowsNeeded <= numArrows && score > maxScore) {
            maxScore = score;
            bestMask = mask;
        }
    }
    
    let bobArrows = new Array(12).fill(0);
    let remainingArrows = numArrows;
    
    for (let i = 0; i < 12; i++) {
        if (bestMask & (1 << i)) {
            bobArrows[i] = aliceArrows[i] + 1;
            remainingArrows -= bobArrows[i];
        }
    }
    
    // 将剩余的箭分配给得分为0的区域
    bobArrows[0] += remainingArrows;
    
    return bobArrows;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(2^12) = O(4096)，需要枚举所有可能的获胜组合
空间复杂度O(1)，只使用了常数额外空间

相关题目