这是 LeetCode 3661 的 C++ 实现，使用记忆化搜索 + 二分查找。

题目思路

1. 排序：将机器人按位置排序，墙壁也排序
2. 预处理：对每个机器人，用二分查找预处理其向左/向右射击能覆盖的墙壁范围
3. 记忆化搜索：`dfs(i, j)` 表示考虑前 `i` 个机器人，第 `i+1` 个机器人的射击方向为 `j`（0=左，1=右）时，能摧毁的最大墙壁数
4. 关键约束：子弹会被相邻机器人挡住，因此当前机器人向右射击时，右边界受下一个机器人影响

C++ 代码

```cpp
#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int maxWalls(vector<int>& robots, vector<int>& distance, vector<int>& walls) {
        int n = robots.size();
        // 将机器人与射程配对，并按位置排序
        vector<pair<int, int>> arr(n);
        for (int i = 0; i < n; i++) {
            arr[i] = {robots[i], distance[i]};
        }
        ranges::sort(arr, {}, &pair<int, int>::first);
        ranges::sort(walls);

        // f[i][j]: 考虑前i个机器人，第i+1个机器人方向为j时的最大摧毁数
        // j=0: 下一个机器人向左射；j=1: 下一个机器人向右射
        vector f(n, vector<int>(2, -1));

        auto dfs = [&](this auto&& dfs, int i, int j) -> int {
            if (i < 0) {
                return 0;
            }
            if (f[i][j] != -1) {
                return f[i][j];
            }

            // 选项1：当前机器人向左射击
            // 左边界 = max(机器人位置 - 射程, 左边机器人位置 + 1)
            // 因为左边机器人也在当前位置，子弹不能穿过它
            int left = arr[i].first - arr[i].second;
            if (i > 0) {
                left = max(left, arr[i - 1].first + 1);
            }
            // 二分查找 [left, robot[i]] 范围内的墙壁数
            int l = ranges::lower_bound(walls, left) - walls.begin();
            int r = ranges::lower_bound(walls, arr[i].first + 1) - walls.begin();
            int ans = dfs(i - 1, 0) + (r - l);

            // 选项2：当前机器人向右射击
            // 右边界受下一个机器人影响
            int right = arr[i].first + arr[i].second;
            if (i + 1 < n) {
                if (j == 0) {
                    // 下一个机器人向左射，其左边界会挡住当前子弹
                    right = min(right, arr[i + 1].first - arr[i + 1].second - 1);
                } else {
                    // 下一个机器人向右射，只需不穿过其位置
                    right = min(right, arr[i + 1].first - 1);
                }
            }
            // 二分查找 [robot[i], right] 范围内的墙壁数
            l = ranges::lower_bound(walls, arr[i].first) - walls.begin();
            r = ranges::lower_bound(walls, right + 1) - walls.begin();
            ans = max(ans, dfs(i - 1, 1) + (r - l));

            return f[i][j] = ans;
        };

        // 从最后一个机器人开始，假设它右边没有机器人（j=1不影响）
        return dfs(n - 1, 1);
    }
};
```

复杂度分析

- 时间复杂度：O(n \log n + m \log m)，其中 n 为机器人数量，m 为墙壁数量。排序 O(n \log n + m \log m)，每个状态 O(\log m) 二分查找，共 O(n) 个状态。
- 空间复杂度：O(n + m)，记忆化数组 O(n)，排序后数组 O(n + m)。

关键点解释

状态    含义    
`dfs(i, 0)`    第 `i` 个机器人向左射，第 `i+1` 个机器人也向左射时的最优解    
`dfs(i, 1)`    第 `i` 个机器人向右射，第 `i+1` 个机器人向右射时的最优解    

为什么向左射时只需考虑左边相邻机器人？
- 子弹从当前机器人向左飞，只会被紧邻的左边机器人挡住（如果那个机器人向右射的话）
- 如果左边机器人向左射，它的子弹往左飞，不会挡住当前子弹

为什么 `j` 参数表示"下一个机器人的方向"？
- 当前机器人向右射时，子弹往右飞，可能会被右边相邻机器人挡住
- 如果右边机器人向左射（`j=0`），它的左边界 `robot[i+1] - distance[i+1]` 是硬边界
- 如果右边机器人向右射（`j=1`），只需保证子弹不穿过 `robot[i+1]` 的位置即可