基于离散化与线段树的机器人摧毁墙壁最大数量解法

正确解法

某个向右的机器人和某个向左的机器人射程重叠后。向右的机器人射程不变，向左的机器人缩短射程使之不重叠。向右射击仍然是一种状态，故只讨论向左。 令向左的机器人位于 x2，向左能射击到 x1。 则：射程非最大向左的最大值为 max_{x1}^{x2-1}( dp[x] + f(x) )，其中 f(x) 是处于 x+1 ~ x2 的墙数，令 g(x) 是 ≤ x 的墙数。 则 射程非最大向左的最大值为 max_{x1}^{x2-1}( dp[x] + g(x2) - g(x) ) = g(x2) + max_{x1}^{x2-1}( dp[x] - g(x) ) 我们用最大值线段树 maxTree2 记录：dp[x]-g(x) 向左射击的最大值为：max(射程非最大向左的最大值，射程最大向左的最大值)

向右也要枚举

比如：

robots ={3,5}, distance ={2,2}, walls ={4,6};

令向右的机器人在 x2，向右能射击到 x3。为了避免和前面的机器人重叠，我将此机器人的射程调整为：x+1 → x3 则起点非 x2 向右的最大值为：max_{x:x2}^{x3-1} dp[x] + (x+1 ~ x3) 的墙的个数 = g(x3) + max_{x:x2}^{x3-1}(dp[x]-g(x)) 可以共用：maxTree2。

内存超限代码

// ... (包含 CSetMaxLineTree 等类的完整实现)

空间超限的解决方法

一，离散化。 二，改用最大值树状数组。

核心代码

template<class T=int> class CDiscretize {
public:
    CDiscretize(vector<T> nums){
        sort(nums.begin(), nums.end()); 
        nums.erase(std::unique(nums.begin(), nums.end()), nums.end()); 
        m_nums = nums;
        for(int i = 0; i < nums.size(); i++){ m_mValueToIndex[nums[i]] = i; }
    }
    // ... 其他方法
};
// ... (包含 Solution 类及 Init 方法)

单元测试

vector<int> robots, distance, walls;
TEST_METHOD(TestMethod00){ 
    robots ={4,10}, distance ={3,3}, walls ={6,7,8};
    auto res =Solution().maxWalls(robots, distance, walls);
    AssertEx(3, res);
}
// ... 更多测试用例

简单版

性质一：如果机器人和墙挨着一起，此墙一定被摧毁。故只考虑不挨着机器人的墙。 性质二：由于子弹遇到机器人会停止，故墙只会被相邻的机器人摧毁。

动态规划的状态表示

dp0n 表示第 0 ~ i 号机器人都已经射击完毕，且最后一个机器人向左（右) 射击能摧毁最后的墙数。 空间复杂度：O(n) 为了方便处理边界情况，增加一个机器人标兵，射击距离都是 0，位置分别在正负无穷大。

动态规划的填表顺序

n = 1 to N 枚举后继状态和选择。

动态规划的转移方程

如果 i-1 和 i 都向左射击，两者不会摧毁同一道墙。 如果 i-1 向右和 i 向左射击，两者可能摧毁同一道墙。需要出度重复。i 向右能够摧毁 g1 道墙，i-1 向左能够摧毁 g0 道墙，i 和 i-1 之间的机器人数量 c，则重复的墙数为：max(0,g1+g0-c)。 如果 i 向右射击，i-1 无论向左还是向右，两者都不会摧毁同一道墙。

动态规划的初始值

全为 0。

动态规划的返回值

max(dp0.back(),dp1.back())

代码

class Solution{
public:
    int maxWalls(vector<int>& robots, vector<int>& distance, vector<int>& walls){
        const int N = robots.size();
        const int M = int(1e9+1e5+1);
        sort(walls.begin(), walls.end()); 
        vector<pair<int,int>> rd;
        for(int i = 0; i < N; i++){ rd.emplace_back(robots[i], distance[i]); }
        rd.emplace_back(INT_MIN /2,0); rd.emplace_back(INT_MAX /2,0);
        sort(rd.begin(), rd.end()); 
        // ... 逻辑实现
    }
};

测试环境

操作系统：win7 开发环境：VS2019 C++17 或者 操作系统：win10 开发环境：VS2022 C++17 如无特殊说明，本算法用 C++ 实现。