列表

详情

2212. 射箭比赛中的最大得分

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 分。

给你整数 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 更高的分数。

 

提示：

原站题解

去查看

上次编辑到这里，代码来自缓存 点击恢复默认模板
class Solution { public: vector<int> maximumBobPoints(int numArrows, vector<int>& aliceArrows) { } };

python3 解法, 执行用时: 844 ms, 内存消耗: 16 MB, 提交时间: 2023-09-14 00:02:47 

class Solution:
    def maximumBobPoints(self, numArrows: int, aliceArrows: List[int]) -> List[int]:
        n = len(aliceArrows)
        maxscore = 0   # 可行的最大得分
        state = 0   # 对应状态
        # 枚举所有输赢状态
        for mask in range(2 ** n):
            cnt = 0
            score = 0
            for i in range(n):
                if (mask >> i) & 1:
                    cnt += aliceArrows[i] + 1
                    score += i
            if cnt <= numArrows and score > maxscore:
                # 可行，且更新了当前最大得分
                maxscore = score
                state = mask
        # 通过状态构造一种可行方法
        res = [0] * n
        for i in range(n):
            if (state >> i) & 1:
                res[i] = aliceArrows[i] + 1
                numArrows -= res[i]
        res[0] += numArrows
        return res

cpp 解法, 执行用时: 48 ms, 内存消耗: 10.1 MB, 提交时间: 2023-09-14 00:02:35 

class Solution {
public:
    vector<int> maximumBobPoints(int numArrows, vector<int>& aliceArrows) {
        int n = aliceArrows.size();
        int maxscore = 0;   // 可行的最大得分
        int state = 0;   // 对应状态
        // 枚举所有输赢状态
        for (int mask = 0; mask < (1 << n); ++mask) {
            int cnt = 0;
            int score = 0;
            for (int i = 0; i < n; ++i) {
                if ((mask >> i) & 1) {
                    cnt += aliceArrows[i] + 1;
                    score += i;
                }
            }
            if (cnt <= numArrows && score > maxscore) {
                // 可行，且更新了当前最大得分
                maxscore = score;
                state = mask;
            }
        }
        // 通过状态构造一种可行方法
        vector<int> res(n);
        for (int i = 0; i < n; ++i) {
            if ((state >> i) & 1) {
                res[i] = aliceArrows[i] + 1;
                numArrows -= res[i];
            }
        }
        res[0] += numArrows;
        return res;
    }
};

java 解法, 执行用时: 43 ms, 内存消耗: 42.9 MB, 提交时间: 2023-09-14 00:02:17 

class Solution {
    public int[] maximumBobPoints(int numArrows, int[] aliceArrows) {
        int n = 12;
        int maxScore = 0;
        int[] res = new int[n];

        for(int i = 0; i < 1 << n; ++i) { // 即i < 2^12
        // 用i来表示每一次结果，i是一个12位的二进制串，如100000000011表示第0、1、11个区域获胜，其他区域都失败
            int score = 0;
            int usedArrows = 0;
            int[] bobArrows = new int[n];
            for(int j = 0; j < 12; ++j) {
                if((i >> j & 1) == 1) { // 若i右移j位后再与1的结果为1，即若i的第j位为1
                    score += j; // 得分
                    usedArrows += aliceArrows[j] + 1; // 使用箭(保证获胜即可，只多射一支箭)
                    bobArrows[j] = aliceArrows[j] + 1; // 记录箭使用的区域和数量
                }
            }
            if(usedArrows > numArrows) { // 若已使用的箭超出了箭的总量
                continue;
            }

            if(score > maxScore) {
                maxScore = score;
                bobArrows[0] += (numArrows - usedArrows); // 没用完的箭随意放在第一个区域
                res = bobArrows; // 数组复制
            }
        }
        return res;
    }
}

rust 解法, 执行用时: 260 ms, 内存消耗: 12.1 MB, 提交时间: 2023-09-14 00:01:25 

impl Solution {
    pub fn maximum_bob_points(num_arrows: i32, alice_arrows: Vec<i32>) -> Vec<i32> {
        /*
        0-1
        dp[0, w] = 0
        dp[i, w] = dp[i-1, w] // alice_arrows[i] >= w
        dp[i, w] = max(dp[i-1, w], dp[i-1, w-alice_arrows[i]-1] + i)
        */
        let num_arrows = num_arrows as usize;
        let mut dp = vec![vec![0; num_arrows+1]; 13];
        for i in 0..=num_arrows {
            dp[0][i] = 0;
        }
        for i in 1..13 {
            for j in 0..=num_arrows {
                if alice_arrows[i-1] >= j as i32 {
                    dp[i][j] = dp[i-1][j];
                } else {
                    dp[i][j] = dp[i-1][j].max(dp[i-1][j-alice_arrows[i-1] as usize-1]+i-1);
                }
            }
        }
        let mut ans = vec![0; alice_arrows.len()];
        let mut w = num_arrows;
        for i in (1..13).rev() {
            if w == 0 {
                break;
            }
            if dp[i][w] > dp[i-1][w] {
                ans[i-1] = alice_arrows[i-1]+1;
                w -= ans[i-1] as usize;
            }
        }
        ans[0] = w as i32;
        ans
    }
}

上一题

© 2024 leetcode.cn