题目描述
一条无限长的直线上分布着一些机器人和墙壁。给定整数数组 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 <= 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 的墙，最后能销毁多少堵墙。按机器人位置从小到大处理，枚举向左或向右射击状态。
错误原因：两个机器人的射击范围不能重叠，否则会重复统计。例如 robots = {4,10}, distance = {3,3}, walls = {6,7,8}。第二个机器人向左射击能到 {7,8,9,10}，第一个机器人向右射击到 7，第二个机器人向左射击到 8，若简单叠加会导致重复计算。
正确解法
核心思想：某个向右的机器人和某个向左的机器人射程重叠后，向右的机器人射程不变，向左的机器人缩短射程使之不重叠。向右射击仍然是一种状态，故主要讨论向左。
令向左的机器人位于 x2，向左能射击到 x1。则射程非最大向左的最大值为 max(dp[x] + f(x))，其中 f(x) 是处于 x+1 ~ x2 的墙数。令 g(x) 是 ≤ x 的墙数。则公式可转化为 g(x2) + max(dp[x] - g(x))。我们用最大值线段树记录 dp[x] - g(x)。
同时需要考虑内存限制。坐标范围可达 10^9，直接开数组会超限。解决方法包括：
- 离散化：将关键坐标映射到小范围索引。
- 改用最大值树状数组或优化线段树实现。
空间优化
通过离散化处理坐标，将大范围坐标压缩到 N 级别，配合线段树进行区间查询和单点更新，从而满足内存限制。
代码实现
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <tuple>
using namespace std;
template<class T = int>
class CDiscretize {
public:
CDiscretize(vector<T> nums) {
sort(nums.begin(), nums.end());
nums.erase(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;
};
template<class TSave, class TRecord>
class CSingeUpdateLineTree {
protected:
virtual void OnQuery(TSave& ans, const TSave& cur) = 0;
virtual void OnUpdate(TSave& save, int iSave, const TRecord& update) = 0;
virtual void OnUpdateParent(TSave& par, const TSave& left, const TSave& r, int iSaveLeft, int iSaveRight) = 0;
};
template<class TSave, class TRecord>
class CVectorSingUpdateLineTree : public CSingeUpdateLineTree<TSave, TRecord> {
public:
CVectorSingUpdateLineTree(int iEleSize, TSave tDefault) : m_iEleSize(iEleSize), m_save(iEleSize * 4, tDefault), m_tDefault(tDefault) {}
void Update(int index, TRecord update) { Update(1, 0, m_iEleSize - 1, index, update); }
TSave Query(int leftIndex, int rightIndex, TSave tDefault) {
TSave ans = tDefault;
Query(ans, 1, 0, m_iEleSize - 1, leftIndex, rightIndex);
return ans;
}
TSave Query(int leftIndex, int rightIndex) { return Query(leftIndex, rightIndex, m_tDefault); }
TSave QueryAll() { return m_save[1]; }
protected:
int m_iEleSize;
void Query(TSave& ans, int iNodeNO, int iSaveLeft, int iSaveRight, int iQueryLeft, int iQueryRight) {
if ((iSaveLeft >= iQueryLeft) && (iSaveRight <= iQueryRight)) {
this->OnQuery(ans, m_save[iNodeNO]);
return;
}
if (iSaveLeft == iSaveRight) return;
const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;
if (mid >= iQueryLeft) Query(ans, iNodeNO * 2, iSaveLeft, mid, iQueryLeft, iQueryRight);
if (mid + 1 <= iQueryRight) Query(ans, iNodeNO * 2 + 1, mid + 1, iSaveRight, iQueryLeft, iQueryRight);
}
void Update(int iNodeNO, int iSaveLeft, int iSaveRight, int iUpdateNO, TRecord update) {
if (iSaveLeft == iSaveRight) {
this->OnUpdate(m_save[iNodeNO], iSaveLeft, update);
return;
}
const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;
if (iUpdateNO <= mid) Update(iNodeNO * 2, iSaveLeft, mid, iUpdateNO, update);
else Update(iNodeNO * 2 + 1, mid + 1, iSaveRight, iUpdateNO, update);
this->OnUpdateParent(m_save[iNodeNO], m_save[iNodeNO * 2], m_save[iNodeNO * 2 + 1], iSaveLeft, iSaveRight);
}
vector<TSave> m_save;
const TSave m_tDefault;
};
template<class TSave, class TRecord>
class CSetMaxLineTree : public CVectorSingUpdateLineTree<TSave, TRecord> {
public:
using CVectorSingUpdateLineTree<TSave, TRecord>::CVectorSingUpdateLineTree;
protected:
virtual void OnQuery(TSave& ans, const TSave& cur) { ans = max(ans, cur); }
virtual void OnUpdate(TSave& save, int iSave, const TRecord& updatee) { save = max(save, updatee); }
virtual void OnUpdateParent(TSave& par, const TSave& left, const TSave& r, int iSaveLeft, int iSaveRight) { par = max(left, r); }
};
class Solution {
public:
int maxWalls(vector<int>& robots, vector<int>& distance, vector<int>& walls) {
int N = robots.size();
Init(robots, distance, walls);
CSetMaxLineTree<int, int> maxTree(M + 1, 0);
CSetMaxLineTree<int, int> maxTree2(M + 1, -1000000);
for (const auto& [x1, x2, x3] : m_xs) {
int g2 = upper_bound(walls.begin(), walls.end(), x2) - walls.begin();
int g3 = upper_bound(walls.begin(), walls.end(), x3) - walls.begin();
int cnt1 = upper_bound(walls.begin(), walls.end(), x2) - lower_bound(walls.begin(), walls.end(), x1);
int left = maxTree.Query(0, x1 - 1) + cnt1;
int cnt2 = upper_bound(walls.begin(), walls.end(), x3) - lower_bound(walls.begin(), walls.end(), x2);
int right = maxTree.Query(0, x2 - 1) + cnt2;
int left2 = maxTree2.Query(x1, x2 - 1) + g2;
int right2 = maxTree2.Query(x2, x3 - 1) + g3;
maxTree.Update(x2, max(left, left2));
maxTree.Update(x3, max(right, right2));
maxTree2.Update(x2, max(left, left2) - g2);
maxTree2.Update(x3, max(right, right2) - g3);
}
return maxTree.QueryAll();
}
private:
int N, M;
vector<tuple<int, int, int>> m_xs;
void Init(const vector<int>& robots, const vector<int>& distance, vector<int>& walls) {
vector<pair<int, int>> rd;
sort(walls.begin(), walls.end());
auto tmp = walls;
tmp.emplace_back(INT_MIN / 2);
for (int i = 0; i < N; i++) {
rd.emplace_back(robots[i], distance[i]);
tmp.emplace_back(robots[i]);
}
CDiscretize<int> disc(tmp);
for (auto& i : walls) {
i = disc[i];
}
sort(rd.begin(), rd.end());
for (int i = 0; i < N; i++) {
const auto& [pos, dis] = rd[i];
const int iLeftRobot = i ? rd[i - 1].first : 1;
const int iLeft = max(iLeftRobot, pos - dis);
const int iRightRobot = (i + 1 == N) ? (INT_MAX / 2) : rd[i + 1].first;
const int iRight = min(iRightRobot, pos + dis);
const int x1 = lower_bound(disc.m_nums.begin(), disc.m_nums.end(), iLeft) - disc.m_nums.begin();
const int x2 = disc[pos];
const int x3 = upper_bound(disc.m_nums.begin(), disc.m_nums.end(), iRight) - disc.m_nums.begin() - 1;
m_xs.emplace_back(x1, x2, x3);
}
M = disc.m_nums.size();
}
};