3661. 可以被机器人摧毁的最大墙壁数目：离散化与动态规划实战

#include <vector>
#include <algorithm>
#include <map>

using namespace std;

class Solution {
public:
    int maxWalls(vector<int>& robots, vector<int>& distance, vector<int>& walls) {
        int n = robots.size();
        // 排序墙壁以便二分查找
        sort(walls.begin(), walls.end());
        
        // 将机器人和距离打包并排序
        vector<pair<int, int>> rd(n);
        for (int i = 0; i < n; ++i) {
            rd[i] = {robots[i], distance[i]};
        }
        sort(rd.begin(), rd.end());
        
        // 离散化关键坐标
        vector<int> coords;
        for (const auto& p : rd) {
            coords.push_back(p.first);
            coords.push_back(p.first - p.second);
            coords.push_back(p.first + p.second);
        }
        for (int w : walls) {
            coords.push_back(w);
        }
        sort(coords.begin(), coords.end());
        coords.erase(unique(coords.begin(), coords.end()), coords.end());
        
        auto getIdx = [&](int val) {
            return lower_bound(coords.begin(), coords.end(), val) - coords.begin();
        };
        
        int m = coords.size();
        // dp[i][0]: 向左，dp[i][1]: 向右
        vector<vector<int>> dp(n, vector<int>(2, 0));
        
        // 辅助函数：计算区间内的墙数量
        auto countWalls = [&](int l, int r) {
            if (l > r) return 0;
            return upper_bound(walls.begin(), walls.end(), r) - lower_bound(walls.begin(), walls.end(), l);
        };
        
        for (int i = 0; i < n; ++i) {
            int pos = rd[i].first;
            int dis = rd[i].second;
            
            // 确定有效射程范围
            int leftBound = (i == 0) ? INT_MIN : rd[i-1].first;
            int rightBound = (i == n - 1) ? INT_MAX : rd[i+1].first;
            
            int lRange = max(leftBound, pos - dis);
            int rRange = min(rightBound, pos + dis);
            
            // 计算向左射击能摧毁的墙
            // 注意：向左射击时，不能越过左边的机器人
            int cntLeft = countWalls(lRange, pos);
            
            // 计算向右射击能摧毁的墙
            int cntRight = countWalls(pos, rRange);
            
            // 状态转移
            // 向左：可以从上一个向左或向右的状态转移过来
            int prevLeft = (i > 0) ? dp[i-1][0] : 0;
            int prevRight = (i > 0) ? dp[i-1][1] : 0;
            
            // 如果前一个向右，当前向左，检查是否有重叠墙
            int overlap = 0;
            if (i > 0 && rd[i-1].first < pos) {
                // 前一个向右的范围是 [rd[i-1].first, rd[i-1].first + rd[i-1].second]
                // 当前向左的范围是 [pos - dis, pos]
                // 重叠区间为 [max(prevRStart, currLStart), min(prevREnd, currLEnd)]
                int prevREnd = rd[i-1].first + rd[i-1].second;
                int currLStart = pos - dis;
                int overlapEnd = min(prevREnd, pos);
                int overlapStart = max(rd[i-1].first, currLStart);
                if (overlapStart <= overlapEnd) {
                    overlap = countWalls(overlapStart, overlapEnd);
                }
            }
            
            dp[i][0] = max(prevLeft, prevRight) + cntLeft - overlap;
            dp[i][1] = max(prevLeft, prevRight) + cntRight;
        }
        
        return max(dp[n-1][0], dp[n-1][1]);
    }
};

测试用例验证

为了确保逻辑正确，建议覆盖以下场景：

1. 单机器人：仅有一个机器人，测试左右射击选择。
2. 多机器人无遮挡：机器人间距足够大，互不影响。
3. 完全遮挡：机器人密集，子弹无法穿过。
4. 边界情况：墙壁与机器人重合。

例如：

• 输入：robots = [4], distance = [3], walls = [1, 10] → 输出：1
• 输入：robots = [10, 2], distance = [5, 1], walls = [5, 2, 7] → 输出：3

通过上述逻辑，我们可以在 $O(N ext{log} N)$ 的时间复杂度内解决问题，同时避免了因坐标过大导致的内存溢出。