射箭比赛中的最大得分 图解题解

这道题到底在问什么

输入

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](总分 4+5+8+9+10+11 = 47)

输入

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](总分 8+9+10 = 27)

先想最直接的笨办法

记牢这套:打第 k 区要 alice[k]+1 支箭、赚 k 分;枚举每个子集算花箭和得分,箭够用里挑得分最高;余箭塞第 0 区。下面按这套一个子集一个子集地试。（动画第 3 步）

最优解：一步一步想明白

1. 3记牢这套:打第 k 区要 alice[k]+1 支箭、赚 k 分;枚举每个子集算花箭和得分,箭够用里挑得分最高;余箭塞第 0 区。下面按这套一个子集一个子集地试。
2. 4先把 Alice 的箭数摆出来。第 0 到第 4 共 5 个区,格子里的数字是 Alice 在这个区射的箭数,格子的位置就是区号,也正好是打赢它能拿的分。右边这张小表把每个区的得分和 Bob 打赢它要的箭都列好了。Bob 手上一共 8 支箭,任务是把它们分配得让总分最高。
3. 5先看要花多少箭。第 4 区 Alice 射了 3 支,Bob 想赢就得严格多于她,至少 4 支,因为打平的话这个区归 Alice。同理第 0 区要 1 支、第 1 区要 2 支、第 2 和第 3 区各要 3 支。右表最后一列就是这几个数。可惜 Bob 只有 8 支箭,不可能每个区都拿下,得挑着来。
4. 6有个区要特别说一下:第 0 区。就算 Bob 赢了它,也只加 0 分,花箭去打它纯属浪费。所以真正值得争的是第 1 到第 4 区。第 0 区的用处是最后收尾:Bob 的箭必须全部射完、总数正好等于 numArrows,挑完区如果还剩箭,就全塞进第 0 区,反正不影响得分。心里有了这些,开始一个一个子集地试。
5. 7试试打第1区、第2区、第3区、第4区这一组,绿色标出来。把它们要的箭加起来:2 + 3 + 3 + 4 = 12 支。手上预算是 8 支,先看看够不够。
6. 8算下来要 12 支箭,已经超过预算 8 支了,标红。箭根本不够,这一组直接淘汰,连得分都不用算。可见区选得越多、越贪,花箭涨得越快,预算这道坎必须先过。
7. 9试试打第2区、第3区、第4区这一组,绿色标出来。把它们要的箭加起来:3 + 3 + 4 = 10 支。手上预算是 8 支,先看看够不够。
8. 10算下来要 10 支箭,已经超过预算 8 支了,标红。箭根本不够,这一组直接淘汰,连得分都不用算。可见区选得越多、越贪,花箭涨得越快,预算这道坎必须先过。
9. 11试试打第3区、第4区这一组,绿色标出来。把它们要的箭加起来:3 + 4 = 7 支。手上预算是 8 支,先看看够不够。
10. 12这组箭够用,花 7 支。算得分:3 + 4 = 7 分。比之前记的 best 还高,把最好成绩刷新成 7 分,先记住打的是第3区、第4区。
11. 13试试打第2区、第4区这一组,绿色标出来。把它们要的箭加起来:3 + 4 = 7 支。手上预算是 8 支,先看看够不够。
12. 14这组箭够用,花 7 支。算得分:2 + 4 = 6 分。不如现在手里的 best 7 分,留着旧的不动。可行不等于最优,得分说了算。
13. 15试试打第1区、第3区、第4区这一组,绿色标出来。把它们要的箭加起来:2 + 3 + 4 = 9 支。手上预算是 8 支,先看看够不够。
14. 16算下来要 9 支箭,已经超过预算 8 支了,标红。箭根本不够,这一组直接淘汰,连得分都不用算。可见区选得越多、越贪,花箭涨得越快,预算这道坎必须先过。
15. 17试试打第1区、第2区、第3区这一组,绿色标出来。把它们要的箭加起来:2 + 3 + 3 = 8 支。手上预算是 8 支,先看看够不够。
16. 18这组箭够用,花 8 支。算得分:1 + 2 + 3 = 6 分。不如现在手里的 best 7 分,留着旧的不动。可行不等于最优,得分说了算。
17. 19试试打第2区、第3区这一组,绿色标出来。把它们要的箭加起来:3 + 3 = 6 支。手上预算是 8 支,先看看够不够。
18. 20这组箭够用,花 6 支。算得分:2 + 3 = 5 分。不如现在手里的 best 7 分,留着旧的不动。可行不等于最优,得分说了算。
19. 21试试打第4区这一组,绿色标出来。把它们要的箭加起来:4 = 4 支。手上预算是 8 支,先看看够不够。
20. 22这组箭够用,花 4 支。算得分:4 = 4 分。不如现在手里的 best 7 分,留着旧的不动。可行不等于最优,得分说了算。
21. 23有代表性的子集都试过了,得分最高的是打第3区、第4区,共 7 分,花 7 支箭。别的组要么超支、要么得分更低,都灰掉了。真实的参考代码会把全部子集都枚举一遍,道理和这里一模一样。接下来把这个选择翻译成 Bob 的箭数分配。
22. 24先给中选的区落箭。要压过 Alice,就射她的箭数加一支:第3区 Alice 2 支,Bob 射 3 支;第4区 Alice 3 支,Bob 射 4 支。加起来投了 7 支,手里还剩 1 支没射出去。
23. 25箭必须全部射完,总数得正好等于 8。现在还剩 1 支,全塞进第 0 区,那里赢了也只加 0 分,塞多少都不影响 Bob 的总分。第 0 区现在有 1 支。这么一来 Bob 的箭刚好射满,得分仍然是 7 分。
24. 26Bob 的分配就出来了:bobArrows = [1, 0, 0, 3, 4]。第 3、第 4 区各比 Alice 多一支、稳稳拿下,得 3 加 4 共 7 分;剩下的箭堆在第 0 区不亏分。箭总数 8 支正好用满。这就是这组小例子的最优解,套到 12 个区上思路完全一样。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from 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

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
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;
    }
};

import java.util.*;
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;
    }
}

复杂度

面试官可能追问