射箭比赛中的最大得分
难度:
标签:
题目描述
Alice 和 Bob 是一场射箭比赛中的对手。比赛规则如下：
- Alice 先射
numArrows支箭，然后 Bob 也射numArrows支箭。 - 分数按下述规则计算：
- 箭靶有若干整数计分区域，范围从
0到11（含0和11）。 - 箭靶上每个区域都对应一个得分
k（范围是0到11），Alice 和 Bob 分别在得分k区域射中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 ，该数组表示 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 <= 105aliceArrows.length == bobArrows.length == 120 <= aliceArrows[i], bobArrows[i] <= numArrowssum(aliceArrows[i]) == numArrows
代码结果
运行时间: 36 ms, 内存: 16.2 MB
// This solution also aims to maximize Bob's score using Java Streams.
// However, the logic for combinatorial generation and selection remains similar to the previous non-stream solution.
// Due to the nature of the problem, Java Streams may not provide significant benefit here.
import java.util.stream.IntStream;
public class Solution {
public int[] maxBobPoints(int numArrows, int[] aliceArrows) {
int[] bobArrows = new int[12];
int maxPoints = 0;
int[] bestBobArrows = new int[12];
int combinations = 1 << 12;
IntStream.range(0, combinations).forEach(i -> {
int sumArrows = 0;
int points = 0;
int[] currentBobArrows = new int[12];
for (int j = 0; j < 12; j++) {
if ((i & (1 << j)) != 0) {
currentBobArrows[j] = aliceArrows[j] + 1;
sumArrows += currentBobArrows[j];
points += j;
}
}
if (sumArrows <= numArrows && points > maxPoints) {
maxPoints = points;
System.arraycopy(currentBobArrows, 0, bestBobArrows, 0, 12);
}
});
int totalUsedArrows = IntStream.of(bestBobArrows).sum();
if (totalUsedArrows < numArrows) {
bestBobArrows[0] += numArrows - totalUsedArrows;
}
return bestBobArrows;
}
}解释
方法:
这道题解采用了深度优先搜索(DFS)的方法，从高分到低分区域进行遍历。我们试图确定Bob在每个得分区间应该射出多少箭以最大化他的总分。如果Bob想在某个得分k的区域获得分数，他必须射出的箭数要比Alice多至少一箭。因此，我们首先检查Bob是否有足够的箭来在这个区域得分（即箭数要大于Alice在该区域的箭数），然后决定是否投入箭数超过Alice，以抢夺这个得分区域。这种方法使用了剪枝技术，当确定接下来即使所有区域都得分，总得分还是无法超过当前已知的最大得分时，就停止进一步搜索。
时间复杂度:
O(2^12)
空间复杂度:
O(12)
代码细节讲解
🦆
题解中提到的剪枝策略`(i + 1) * i // 2 + s <= max_sum`是如何计算的，它背后的数学原理是什么？
▷🦆
DFS递归时，为什么会选择从得分高的区域开始向低得分区域递归，这种策略的优势在哪里？
▷🦆
在DFS的递归过程中，为什么要对`path`进行反转操作，这样做的目的是什么？
▷