离散化与线段树解决机器人摧毁墙壁问题

题目描述

一条无限长的直线上分布着一些机器人和墙壁。给定整数数组 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，直接开数组会超限。解决方法包括：

1. 离散化：将关键坐标映射到小范围索引。
2. 改用最大值树状数组或优化线段树实现。

空间优化

通过离散化处理坐标，将大范围坐标压缩到 N 级别，配合线段树进行区间查询和单点更新，从而满足内存限制。

代码实现

#include <vector>
#include <algorithm>
#include <unordered_map>
#include <tuple>

using namespace std;

template<class T = int>
class CDiscretize {
public:
    (vector<T> nums) {
        (nums.(), nums.());
        nums.((nums.(), nums.()), nums.());
        m_nums = nums;
         ( i = ; i < nums.(); i++) {
            m_mValueToIndex[nums[i]] = i;
        }
    }
     []( T value)  {
         it = m_mValueToIndex.(value);
         (m_mValueToIndex.() == it)  ;
         it->second;
    }
    {  m_mValueToIndex.(); }
    vector<T> m_nums;
:
    unordered_map<T, > m_mValueToIndex;
};

< ,  >
  {
:
    = ;
    = ;
    = ;
};

< ,  >
  :  CSingeUpdateLineTree<TSave, TRecord> {
:
    ( iEleSize, TSave tDefault) : (iEleSize), (iEleSize * , tDefault), (tDefault) {}
    { (, , m_iEleSize - , index, update); }
    {
        TSave ans = tDefault;
        (ans, , , m_iEleSize - , leftIndex, rightIndex);
         ans;
    }
    {  (leftIndex, rightIndex, m_tDefault); }
    {  m_save[]; }
:
     m_iEleSize;
    {
         ((iSaveLeft >= iQueryLeft) && (iSaveRight <= iQueryRight)) {
            ->(ans, m_save[iNodeNO]);
            ;
        }
         (iSaveLeft == iSaveRight) ;
          mid = iSaveLeft + (iSaveRight - iSaveLeft) / ;
         (mid >= iQueryLeft) (ans, iNodeNO * , iSaveLeft, mid, iQueryLeft, iQueryRight);
         (mid +  <= iQueryRight) (ans, iNodeNO *  + , mid + , iSaveRight, iQueryLeft, iQueryRight);
    }
    {
         (iSaveLeft == iSaveRight) {
            ->(m_save[iNodeNO], iSaveLeft, update);
            ;
        }
          mid = iSaveLeft + (iSaveRight - iSaveLeft) / ;
         (iUpdateNO <= mid) (iNodeNO * , iSaveLeft, mid, iUpdateNO, update);
         (iNodeNO *  + , mid + , iSaveRight, iUpdateNO, update);
        ->(m_save[iNodeNO], m_save[iNodeNO * ], m_save[iNodeNO *  + ], iSaveLeft, iSaveRight);
    }
    vector<TSave> m_save;
     TSave m_tDefault;
};

< ,  >
  :  CVectorSingUpdateLineTree<TSave, TRecord> {
:
     CVectorSingUpdateLineTree<TSave, TRecord>::CVectorSingUpdateLineTree;
:
    { ans = (ans, cur); }
    { save = (save, updatee); }
    { par = (left, r); }
};

  {
:
    {
         N = robots.();
        (robots, distance, walls);
        ;
        ;
         ( & [x1, x2, x3] : m_xs) {
             g2 = (walls.(), walls.(), x2) - walls.();
             g3 = (walls.(), walls.(), x3) - walls.();
             cnt1 = (walls.(), walls.(), x2) - (walls.(), walls.(), x1);
             left = maxTree.(, x1 - ) + cnt1;
             cnt2 = (walls.(), walls.(), x3) - (walls.(), walls.(), x2);
             right = maxTree.(, x2 - ) + cnt2;
             left2 = maxTree(x1, x2 - ) + g2;
             right2 = maxTree(x2, x3 - ) + g3;
            maxTree.(x2, (left, left2));
            maxTree.(x3, (right, right2));
            maxTree(x2, (left, left2) - g2);
            maxTree(x3, (right, right2) - g3);
        }
         maxTree.();
    }

:
     N, M;
    vector<tuple<, , >> m_xs;

    {
        vector<pair<, >> rd;
        (walls.(), walls.());
         tmp = walls;
        tmp.(INT_MIN / );
         ( i = ; i < N; i++) {
            rd.(robots[i], distance[i]);
            tmp.(robots[i]);
        }
        ;
         (& i : walls) {
            i = disc[i];
        }
        (rd.(), rd.());
         ( i = ; i < N; i++) {
             & [pos, dis] = rd[i];
              iLeftRobot = i ? rd[i - ].first : ;
              iLeft = (iLeftRobot, pos - dis);
              iRightRobot = (i +  == N) ? (INT_MAX / ) : rd[i + ].first;
              iRight = (iRightRobot, pos + dis);
              x1 = (disc.m_nums.(), disc.m_nums.(), iLeft) - disc.m_nums.();
              x2 = disc[pos];
              x3 = (disc.m_nums.(), disc.m_nums.(), iRight) - disc.m_nums.() - ;
            m_xs.(x1, x2, x3);
        }
        M = disc.m_nums.();
    }
};