LeetCode 3661 可以被机器人摧毁的最大墙壁数目 - 离散化与线段树解法

正确解法

某个向右的机器人和某个向左的机器人射程重叠后。向右的机器人射程不变，向左的机器人缩短射程使之不重叠。向右射击仍然是一种状态，故只讨论向左。 令向左的机器人位于 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(射程非最大向左的最大值，射程最大向左的最大值)。

内存超限代码

class Solution {
public:
    int maxWalls(vector<int>& robots, vector<int>& distance, vector<int>& walls) {
        const int N = robots.size();
        const int M = (int)(1e9 + 2e5);
        sort(walls.begin(), walls.end());
        // ... (具体实现逻辑)
    }
};

空间超限的解决方法

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

核心代码

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;
        }
    }
    // ... (其他方法)
};

class Solution {
public:
    int maxWalls(vector<int>& robots, vector<int>& distance, vector<int>& walls) {
        N = robots.size();
        Init(robots, distance, walls);
        CSetMaxLineTree<int,int> maxTree(M+1, 0), maxTree2(M+1, -1000'000);
        for(const auto& [x1, x2, x3] : m_xs) {
            // ... (计算逻辑)
        }
        return maxTree.QueryAll();
    }
    // ... (初始化函数)
};

简单版 DP

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

动态规划的状态表示

dp0[n] 表示第 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 无论向左还是向右，两者都不会摧毁同一道墙。

代码

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());
        // ... (DP 逻辑)
    }
};