3661. 可以被机器人摧毁的最大墙壁数目
一条无限长的直线上分布着一些机器人和墙壁。给你整数数组 robots，distance 和 walls：
- robots[i] 是第 i 个机器人的位置。
- distance[i] 是第 i 个机器人的子弹可以行进的最大距离。
- walls[j] 是第 j 堵墙的位置。
每个机器人有一颗子弹，可以向左或向右发射，最远距离为 distance[i] 米。子弹会摧毁其射程内路径上的每一堵墙。机器人是固定的障碍物：如果子弹在到达墙壁前击中另一个机器人，它会立即在该机器人处停止，无法继续前进。
返回机器人可以摧毁墙壁的最大数量。
注意：
- 墙壁和机器人可能在同一位置；该位置的墙壁可以被该位置的机器人摧毁。
- 机器人不会被子弹摧毁。
示例
示例 1: 输入：robots = [4], distance = [3], walls = [1,10] 输出：1 解释：robots[0] = 4 向左发射，distance[0] = 3，覆盖范围 [1, 4]，摧毁了 walls[0] = 1。
示例 2: 输入：robots = [10,2], distance = [5,1], walls = [5,2,7] 输出：3 解释：
- robots[0] = 10 向左发射，distance[0] = 5，覆盖范围 [5, 10]，摧毁了 walls[0] = 5 和 walls[2] = 7。
- robots[1] = 2 向左发射，distance[1] = 1，覆盖范围 [1, 2]，摧毁了 walls[1] = 2。
示例 3: 输入：robots = [1,2], distance = [100,1], walls = [10] 输出：0 解释：在这个例子中，只有 robots[0] 能够到达墙壁，但它向右的射击被 robots[1] 挡住了，因此答案是 0。
错误解法：线段树 + 动态规划
动态规划的状态表示
dp[i] 表示只摧毁位置 ≤ i 的墙，最后能销毁多少堵墙。且之后不会消耗 ≤ i 的墙。 最大值线段树 maxTree 记录最大值。
动态规划的顺序
按机器人的位置从小到大处理。
动态规划的转移方程
每个机器人枚举两种状态，向左射击，向右射击。
错误原因
由于两个机器人的射击范围不能重叠，否则会重复统计。故向左射击不一定是最大射程，各射程要一一枚举。 例如：robots = {4,10}, distance = {3,3}, walls = {6,7,8}。 第二个机器人向左射击能到 {7,8,9,10}。第一个机器人向右射击到 7，第二个机器人向左射击到 8，才是正解。
template<class TSave, class TRecord>
class CRangUpdateLineTree {
protected:
virtual void OnQuery(TSave& ans, const TSave& save, const int& iSaveLeft, const int& iSaveRight) = 0;
virtual void OnUpdate(TSave& save, const int& iSaveLeft, const int& iSaveRight, const TRecord& update) = 0;
// ... (省略部分实现细节)
};
// ... (更多模板类定义)
正确解法
某个向右的机器人和某个向左的机器人射程重叠后。向右的机器人射程不变，向左的机器人缩短射程使之不重叠。向右射击仍然是一种状态，故只讨论向左。 令向左的机器人位于 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 逻辑)
}
};