C++算法
LeetCode 3661 可以被机器人摧毁的最大墙壁数目解法分析
针对 LeetCode 3661 机器人摧毁墙壁问题，核心在于处理机器人射程重叠及子弹被阻挡导致的计数重复。初始方案使用线段树结合动态规划，因坐标范围过大导致内存超限。改进方案引入离散化技术压缩坐标空间，配合最大值线段树优化区间查询。通过定义 dp 状态记录机器人向左或向右射击后的最大得分，利用前缀和计算墙数并减去重叠部分。最终在 O(N log N) 时间内解决问题，有效解决了空间限制并保证了算法正确性。
针对 LeetCode 3661 机器人摧毁墙壁问题，核心在于处理机器人射程重叠及子弹被阻挡导致的计数重复。初始方案使用线段树结合动态规划，因坐标范围过大导致内存超限。改进方案引入离散化技术压缩坐标空间，配合最大值线段树优化区间查询。通过定义 dp 状态记录机器人向左或向右射击后的最大得分，利用前缀和计算墙数并减去重叠部分。最终在 O(N log N) 时间内解决问题，有效解决了空间限制并保证了算法正确性。
一条无限长的直线上分布着一些机器人和墙壁。给你整数数组 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(射程非最大向左的最大值，射程最大向左的最大值)。
比如：robots ={3,5}, distance ={2,2}, walls ={4,6}; 令向右的机器人在 x2，向右能射击到 x3。为了避免和前面的机器人重叠，我将此机器人的射程调整为：x+1 → x3。 则起点非 x2 向右的最大值为：g(x3) + max_{x:x2}^{x3-1}( dp[x]-g(x) )。 可以共用：maxTree2。
template<class TSave,class TRecord>class CSingeUpdateLineTree {
// ... 单点更新线段树实现 ...
};
// ... Solution 类实现 ...
一，离散化。 二，改用最大值树状数组。
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;
};
// ... 结合离散化的 Solution 实现 ...
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);
}
// ... 更多测试用例 ...
性质一：如果机器人和墙挨着一起，此墙一定被摧毁。故只考虑不挨着机器人的墙。 性质二：由于子弹遇到机器人会停止，故墙只会被相邻的机器人摧毁。
dp0[n] / dp1[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 无论向左还是向右，两者都不会摧毁同一道墙。
全为 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++ 实现。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 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