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。因此，答案是 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。
示例 3: 输入：robots = [1,2], distance = [100,1], walls = [10] 输出：0 解释：在这个例子中，只有 robots[0] 能够到达墙壁，但它向右的射击被 robots[1] 挡住了，因此答案是 0。
提示：
- 1 <= robots.length == distance.length <= 10^5
- 1 <= walls.length <= 10^5
- 1 <= robots[i], walls[j] <= 10^9
- 1 <= distance[i] <= 10^5
- robots 中的所有值都是互不相同的
错误解法：线段树 + 动态规划
动态规划的状态表示
dp[i] 表示只摧毁位置 ≤ i 的墙，最后能销毁多少堵墙。且之后不会消耗 ≤ i 的墙。 最大值线段树 maxTree 记录最大值。
动态规划的顺序
按机器人的位置从小到大处理。
动态规划的转移方程
每个机器人枚举两种状态，向左射击，向右射击。
动态规划的初始值
全为 0。
动态规划的返回值
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;
virtual void OnUpdateParent(TSave& par, const TSave& left, const TSave& r, const int& iSaveLeft, const int& iSaveRight) = 0;
virtual void OnUpdateRecord(TRecord& old, const TRecord& newRecord) = 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(x)) + g(x2)。 我们用最大值线段树 maxTree2 记录：dp[x] - g(x)。 向左射击的最大值为：max(射程非最大向左的最大值，射程最大向左的最大值)。
内存超限代码
template<class TSave, class TRecord>
class CSingeUpdateLineTree {
protected:
virtual void OnQuery(TSave& ans, const TSave& cur) = 0;
// ... 实现细节
};
// ... 完整类定义略
空间超限的解决方法
一、离散化。 二、改用最大值树状数组。
核心代码
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;
}
}
int operator[](const T value) const {
auto it = m_mValueToIndex.find(value);
if (m_mValueToIndex.end() == it) return -1;
return it->second;
}
int size() const { return m_mValueToIndex.size(); }
vector<T> m_nums;
protected:
unordered_map<T, int> m_mValueToIndex;
};
// ... 线段树实现略
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();
}
// ... 辅助函数
};
简单版
性质一：如果机器人和墙挨着一起，此墙一定被摧毁。故只考虑不挨着机器人的墙。 性质二：由于子弹遇到机器人会停止，故墙只会被相邻的机器人摧毁。
动态规划的状态表示
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());
// ... 后续逻辑
return cntSamePos + max(dp0[N], dp1[N]);
}
};
