跳转至

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

  • 例如，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

解法

方法一：二进制枚举

思考

Bob 要在 \(12\) 个环上分配箭，某环得分当且仅当箭数严格多于 Alice。若按每环箭数搜索，\(\textit{numArrows}\) 可达 \(10^5\)，状态过多。环数只有 \(12\)，真正要决定的是「赢下哪些环」。

赢下第 \(i\) 环恰好需要 \(aliceArrows[i]+1\) 支箭，得分固定为 \(i\)。因此用长度为 \(12\) 的二进制掩码枚举得分集合，累加所需箭数与得分；箭数不超过限额且得分更优时记下该掩码。

最后按掩码还原各环箭数，剩余箭全部放入 \(0\) 环（该环本不得分）。枚举量 \(2^{12}\)，可以接受。

由于区域数目只有 \(12\) 个，因此我们使用二进制枚举的方式，枚举 \(\textit{Bob}\) 在哪些区域得分。用一个变量 \(\textit{st}\) 表示 \(\textit{Bob}\) 获得最大得分的方案，而 \(\textit{mx}\) 表示 \(\textit{Bob}\) 获得的最大得分。

我们在 \([1, 2^m)\) 的区间内枚举 \(\textit{Bob}\) 的得分方案，其中 \(m\) 是 \(\textit{aliceArrows}\) 的长度。对于每一个方案，我们计算 \(\textit{Bob}\) 的得分 \(\textit{s}\) 以及射箭的数量 \(\textit{cnt}\)。如果 \(\textit{cnt} \leq \textit{numArrows}\) 且 \(\textit{s} > \textit{mx}\)，我们就更新 \(\textit{mx}\) 和 \(\textit{st}\)。

然后，我们根据 \(\textit{st}\) 计算 \(\textit{Bob}\) 的得分方案，如果最后还有剩余的射箭，我们将剩余的射箭分配给第一个区域，即下标为 \(0\) 的区域。

时间复杂度 \(O(2^m \times m)\)，其中 \(m\) 是 \(\textit{aliceArrows}\) 的长度。忽略答案数组的空间消耗，空间复杂度 \(O(1)\)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def maximumBobPoints(self, numArrows: int, aliceArrows: List[int]) -> List[int]:
        st = mx = 0
        m = len(aliceArrows)
        for mask in range(1, 1 << m):
            cnt = s = 0
            for i, x in enumerate(aliceArrows):
                if mask >> i & 1:
                    s += i
                    cnt += x + 1
            if cnt <= numArrows and s > mx:
                mx = s
                st = mask
        ans = [0] * m
        for i, x in enumerate(aliceArrows):
            if st >> i & 1:
                ans[i] = x + 1
                numArrows -= ans[i]
        ans[0] += numArrows
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public int[] maximumBobPoints(int numArrows, int[] aliceArrows) {
        int st = 0, mx = 0;
        int m = aliceArrows.length;
        for (int mask = 1; mask < 1 << m; ++mask) {
            int cnt = 0, s = 0;
            for (int i = 0; i < m; ++i) {
                if ((mask >> i & 1) == 1) {
                    s += i;
                    cnt += aliceArrows[i] + 1;
                }
            }
            if (cnt <= numArrows && s > mx) {
                mx = s;
                st = mask;
            }
        }
        int[] ans = new int[m];
        for (int i = 0; i < m; ++i) {
            if ((st >> i & 1) == 1) {
                ans[i] = aliceArrows[i] + 1;
                numArrows -= ans[i];
            }
        }
        ans[0] += numArrows;
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    vector<int> maximumBobPoints(int numArrows, vector<int>& aliceArrows) {
        int st = 0, mx = 0;
        int m = aliceArrows.size();
        for (int mask = 1; mask < 1 << m; ++mask) {
            int cnt = 0, s = 0;
            for (int i = 0; i < m; ++i) {
                if (mask >> i & 1) {
                    s += i;
                    cnt += aliceArrows[i] + 1;
                }
            }
            if (cnt <= numArrows && s > mx) {
                mx = s;
                st = mask;
            }
        }
        vector<int> ans(m);
        for (int i = 0; i < m; ++i) {
            if (st >> i & 1) {
                ans[i] = aliceArrows[i] + 1;
                numArrows -= ans[i];
            }
        }
        ans[0] += numArrows;
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
func maximumBobPoints(numArrows int, aliceArrows []int) []int {
    st, mx := 0, 0
    m := len(aliceArrows)
    for mask := 1; mask < 1<<m; mask++ {
        cnt, s := 0, 0
        for i, x := range aliceArrows {
            if mask>>i&1 == 1 {
                s += i
                cnt += x + 1
            }
        }
        if cnt <= numArrows && s > mx {
            mx = s
            st = mask
        }
    }
    ans := make([]int, m)
    for i, x := range aliceArrows {
        if (st>>i)&1 == 1 {
            ans[i] = x + 1
            numArrows -= ans[i]
        }
    }
    ans[0] += numArrows
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
function maximumBobPoints(numArrows: number, aliceArrows: number[]): number[] {
    let [st, mx] = [0, 0];
    const m = aliceArrows.length;
    for (let mask = 1; mask < 1 << m; mask++) {
        let [cnt, s] = [0, 0];
        for (let i = 0; i < m; i++) {
            if ((mask >> i) & 1) {
                cnt += aliceArrows[i] + 1;
                s += i;
            }
        }
        if (cnt <= numArrows && s > mx) {
            mx = s;
            st = mask;
        }
    }
    const ans: number[] = Array(m).fill(0);
    for (let i = 0; i < m; i++) {
        if ((st >> i) & 1) {
            ans[i] = aliceArrows[i] + 1;
            numArrows -= ans[i];
        }
    }
    ans[0] += numArrows;
    return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
impl Solution {
    pub fn maximum_bob_points(num_arrows: i32, alice_arrows: Vec<i32>) -> Vec<i32> {
        let mut st = 0;
        let mut mx = 0;
        let m = alice_arrows.len();
        for mask in 1..(1 << m) {
            let mut cnt = 0;
            let mut s = 0;
            for i in 0..m {
                if (mask >> i) & 1 == 1 {
                    s += i as i32;
                    cnt += alice_arrows[i] + 1;
                }
            }
            if cnt <= num_arrows && s > mx {
                mx = s;
                st = mask;
            }
        }
        let mut ans = vec![0; m];
        let mut num_arrows = num_arrows;
        for i in 0..m {
            if (st >> i) & 1 == 1 {
                ans[i] = alice_arrows[i] + 1;
                num_arrows -= ans[i];
            }
        }
        ans[0] += num_arrows;
        ans
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * @param {number} numArrows
 * @param {number[]} aliceArrows
 * @return {number[]}
 */
var maximumBobPoints = function (numArrows, aliceArrows) {
    let [st, mx] = [0, 0];
    const m = aliceArrows.length;
    for (let mask = 1; mask < 1 << m; mask++) {
        let [cnt, s] = [0, 0];
        for (let i = 0; i < m; i++) {
            if ((mask >> i) & 1) {
                cnt += aliceArrows[i] + 1;
                s += i;
            }
        }
        if (cnt <= numArrows && s > mx) {
            mx = s;
            st = mask;
        }
    }
    const ans = Array(m).fill(0);
    for (let i = 0; i < m; i++) {
        if ((st >> i) & 1) {
            ans[i] = aliceArrows[i] + 1;
            numArrows -= ans[i];
        }
    }
    ans[0] += numArrows;
    return ans;
};

评论