C++算法
算法题解：3661 可以被机器人摧毁的最大墙壁数目（离散化、线段树）
对 LeetCode 3661 题，探讨在无限长直线上机器人摧毁墙壁的最大数量问题。由于坐标范围巨大，采用离散化技术压缩空间。核心解法为动态规划配合线段树或树状数组，解决机器人射程重叠导致的重复统计问题。文章对比了错误 DP 方案与正确优化方案，详细推导了状态转移方程，并提供了完整的 C++ 代码实现及单元测试示例。
对 LeetCode 3661 题，探讨在无限长直线上机器人摧毁墙壁的最大数量问题。由于坐标范围巨大，采用离散化技术压缩空间。核心解法为动态规划配合线段树或树状数组，解决机器人射程重叠导致的重复统计问题。文章对比了错误 DP 方案与正确优化方案，详细推导了状态转移方程，并提供了完整的 C++ 代码实现及单元测试示例。
一条无限长的直线上分布着一些机器人和墙壁。给你整数数组 robots，distance 和 walls：
每个机器人有一颗子弹，可以向左或向右发射，最远距离为 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。
提示：
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();
(robots, distance, walls);
;
( & [x1, x2, x3] : m_xs) {
}
maxTree.();
}
};
性质一：如果机器人和墙挨着一起，此墙一定被摧毁。故只考虑不挨着机器人的墙。 性质二：由于子弹遇到机器人会停止，故墙只会被相邻的机器人摧毁。
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]);
}
};
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML 转 Markdown 互为补充。 在线工具，Markdown 转 HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML 转 Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online