题目描述
思路解析动画文字版
记牢这套:打第 k 区要 alice[k]+1 支箭、赚 k 分;枚举每个子集算花箭和得分,箭够用里挑得分最高;余箭塞第 0 区。下面按这套一个子集一个子集地试。
先摆出 Alice 的箭数：先把 Alice 的箭数摆出来。第 0 到第 4 共 5 个区,格子里的数字是 Alice 在这个区射的箭数,格子的位置就是区号,也正好是打赢它能拿的分。右边这张小表把每个区的得分和 Bob 打赢它要的箭都列好了。Bob 手上一共 8 支箭,任务是把它们分配得让总分最高。
打赢一个区要几支箭：先看要花多少箭。第 4 区 Alice 射了 3 支,Bob 想赢就得严格多于她,至少 4 支,因为打平的话这个区归 Alice。同理第 0 区要 1 支、第 1 区要 2 支、第 2 和第 3 区各要 3 支。右表最后一列就是这几个数。可惜 Bob 只有 8 支箭,不可能每个区都拿下,得挑着来。
第 0 区得 0 分,打它是浪费：有个区要特别说一下:第 0 区。就算 Bob 赢了它,也只加 0 分,花箭去打它纯属浪费。所以真正值得争的是第 1 到第 4 区。第 0 区的用处是最后收尾:Bob 的箭必须全部射完、总数正好等于 numArrows,挑完区如果还剩箭,就全塞进第 0 区,反正不影响得分。心里有了这些,开始一个一个子集地试。
试子集 · 打第1区、第2区、第3区、第4区：试试打第1区、第2区、第3区、第4区这一组,绿色标出来。把它们要的箭加起来:2 + 3 + 3 + 4 = 12 支。手上预算是 8 支,先看看够不够。
超支 · 打第1区、第2区、第3区、第4区这组丢弃：算下来要 12 支箭,已经超过预算 8 支了,标红。箭根本不够,这一组直接淘汰,连得分都不用算。可见区选得越多、越贪,花箭涨得越快,预算这道坎必须先过。
试子集 · 打第2区、第3区、第4区：试试打第2区、第3区、第4区这一组,绿色标出来。把它们要的箭加起来:3 + 3 + 4 = 10 支。手上预算是 8 支,先看看够不够。
超支 · 打第2区、第3区、第4区这组丢弃：算下来要 10 支箭,已经超过预算 8 支了,标红。箭根本不够,这一组直接淘汰,连得分都不用算。可见区选得越多、越贪,花箭涨得越快,预算这道坎必须先过。
试子集 · 打第3区、第4区：试试打第3区、第4区这一组,绿色标出来。把它们要的箭加起来:3 + 4 = 7 支。手上预算是 8 支,先看看够不够。
刷新 · 打第3区、第4区得分更高：这组箭够用,花 7 支。算得分:3 + 4 = 7 分。比之前记的 best 还高,把最好成绩刷新成 7 分,先记住打的是第3区、第4区。
试子集 · 打第2区、第4区：试试打第2区、第4区这一组,绿色标出来。把它们要的箭加起来:3 + 4 = 7 支。手上预算是 8 支,先看看够不够。
保留 · 打第2区、第4区不如现有：这组箭够用,花 7 支。算得分:2 + 4 = 6 分。不如现在手里的 best 7 分,留着旧的不动。可行不等于最优,得分说了算。
试子集 · 打第1区、第3区、第4区：试试打第1区、第3区、第4区这一组,绿色标出来。把它们要的箭加起来:2 + 3 + 4 = 9 支。手上预算是 8 支,先看看够不够。
超支 · 打第1区、第3区、第4区这组丢弃：算下来要 9 支箭,已经超过预算 8 支了,标红。箭根本不够,这一组直接淘汰,连得分都不用算。可见区选得越多、越贪,花箭涨得越快,预算这道坎必须先过。
试子集 · 打第1区、第2区、第3区：试试打第1区、第2区、第3区这一组,绿色标出来。把它们要的箭加起来:2 + 3 + 3 = 8 支。手上预算是 8 支,先看看够不够。
保留 · 打第1区、第2区、第3区不如现有：这组箭够用,花 8 支。算得分:1 + 2 + 3 = 6 分。不如现在手里的 best 7 分,留着旧的不动。可行不等于最优,得分说了算。
试子集 · 打第2区、第3区：试试打第2区、第3区这一组,绿色标出来。把它们要的箭加起来:3 + 3 = 6 支。手上预算是 8 支,先看看够不够。
保留 · 打第2区、第3区不如现有：这组箭够用,花 6 支。算得分:2 + 3 = 5 分。不如现在手里的 best 7 分,留着旧的不动。可行不等于最优,得分说了算。
试子集 · 打第4区：试试打第4区这一组,绿色标出来。把它们要的箭加起来:4 = 4 支。手上预算是 8 支,先看看够不够。
保留 · 打第4区不如现有：这组箭够用,花 4 支。算得分:4 = 4 分。不如现在手里的 best 7 分,留着旧的不动。可行不等于最优,得分说了算。
试完 · 最优是打第3区、第4区得 7 分：有代表性的子集都试过了,得分最高的是打第3区、第4区,共 7 分,花 7 支箭。别的组要么超支、要么得分更低,都灰掉了。真实的参考代码会把全部子集都枚举一遍,道理和这里一模一样。接下来把这个选择翻译成 Bob 的箭数分配。
落箭 · 中选区各射 alice+1 支：先给中选的区落箭。要压过 Alice,就射她的箭数加一支:第3区 Alice 2 支,Bob 射 3 支;第4区 Alice 3 支,Bob 射 4 支。加起来投了 7 支,手里还剩 1 支没射出去。
收尾 · 余下 1 支全塞第 0 区：箭必须全部射完,总数得正好等于 8。现在还剩 1 支,全塞进第 0 区,那里赢了也只加 0 分,塞多少都不影响 Bob 的总分。第 0 区现在有 1 支。这么一来 Bob 的箭刚好射满,得分仍然是 7 分。
答案 · bobArrows = [1,0,0,3,4]：Bob 的分配就出来了:bobArrows = [1, 0, 0, 3, 4]。第 3、第 4 区各比 Alice 多一支、稳稳拿下,得 3 加 4 共 7 分;剩下的箭堆在第 0 区不亏分。箭总数 8 支正好用满。这就是这组小例子的最优解,套到 12 个区上思路完全一样。
边界想清:箭少时优先挑能用 1 支拿下的最高分区;Alice 某区为 0 时只要 1 支就能拿下该区,别浪费在第 0 区。
面试重点:区数固定 12 所以子集枚举暴力可行、本质是箭数容量的 0 到 1 背包、余箭塞第 0 区凑满总数。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *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复杂度
- 时间：O(2^m · m)，m 是计分区个数,这里恒等于 12。外层枚举 2 的 12 次方约 4096 个子集,内层每个子集扫 12 位算花箭和得分,合起来约 4096 乘 12 次常数操作。因为 m 固定是 12,整体是一个有上界的常数,不随 numArrows 增长
- 空间：O(m)，按峰值算。除了长度为 12 的答案数组,只用了 mask、s、cnt、mx、st 几个整数变量,没有额外随规模增长的结构,所以额外空间是常数、算上输出是 O(m)
易错点
面试追问把动画讲成自己的话
追问这题为什么能用枚举子集暴力做?
追问除了位掩码,还有别的做法吗?
追问为什么最后要把余箭塞进第 0 区?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
根据模式串构造最小数字
LeetCode 2375 · 中等 · 沿着 回溯套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题