3661 可以被机器人摧毁的最大墙壁数目 - 离散化与线段树解法

正确解法

某个向右的机器人和某个向左的机器人射程重叠后。向右的机器人射程不变，向左的机器人缩短射程使之不重叠。向右射击仍然是一种状态，故只讨论向左。 令向左的机器人位于 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(x2) - g(x)) = g(x2) + max_{x1}^{x2-1}(dp[x] - g(x))。 我们用最大值线段树 maxTree2 记录：dp[x] - g(x)。 向左射击的最大值为：max(射程非最大向左的最大值，射程最大向左的最大值)。

向右也要枚举

比如：robots = {3,5}, distance = {2,2}, walls = {4,6}。 令向右的机器人在 x2，向右能射击到 x3。为了避免和前面的机器人重叠，我将此机器人的射程调整为：x+1 → x3。 则起点非 x2 向右的最大值为：max_{x:x2}^{x3-1} dp[x] + (x+1 ~ x3) 的墙的个数 = g(x3) + max_{x:x2}^{x3-1}(dp[x] - g(x))。 可以共用：maxTree2。

空间超限的解决方法

一、离散化。 二、改用最大值树状数组。

核心代码

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;
};

// ... (CSetMaxLineTree 等实现略，保持原有逻辑)

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) {
            const int g2 = upper_bound(walls.begin(), walls.end(), x2) - walls.begin();
            const int g3 = upper_bound(walls.begin(), walls.end(), x3) - walls.begin();
            const int cnt1 = upper_bound(walls.begin(), walls.end(), x2) - lower_bound(walls.begin(), walls.end(), x1);
            const int left = maxTree.Query(0, x1 - 1) + cnt1;
            const int cnt2 = upper_bound(walls.begin(), walls.end(), x3) - lower_bound(walls.begin(), walls.end(), x2);
            const int right = maxTree.Query(0, x2 - 1) + cnt2;
            const int left2 = maxTree2.Query(x1, x2 - 1) + g2;
            const 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();
    }
    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); // 编码增加 0，实际编码从 1 开始
        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();
    }
    int N, M;
    vector<tuple<int, int, int>> m_xs;
};

单元测试

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);
}
TEST_METHOD(TestMethod11) {
    robots = {4}, distance = {3}, walls = {1,10};
    auto res = Solution().maxWalls(robots, distance, walls);
    AssertEx(1, res);
}
// ... 其他测试用例略

简单版

性质一：如果机器人和墙挨着一起，此墙一定被摧毁。故只考虑不挨着机器人的墙。 性质二：由于子弹遇到机器人会停止，故墙只会被相邻的机器人摧毁。

动态规划的状态表示

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());
        vector<int> vLeft(N + 2), vRight(N + 2);
        for (int i = 0; i < rd.size(); i++) {
            const auto& [pos, dis] = rd[i];
            const int iLeftRobot = i ? rd[i - 1].first : -M;
            vLeft[i] = max(iLeftRobot, pos - dis - 1);
            const int iRightRobot = (i + 1 == N + 2) ? M : rd[i + 1].first;
            vRight[i] = min(iRightRobot, pos + dis + 1);
        }
        auto Cnt = [&](int left, int r) {
            int ans = lower_bound(walls.begin(), walls.end(), r) - upper_bound(walls.begin(), walls.end(), left);
            return ans;
        };
        // （left,r) 之间的墙数量，不包括 left,r。
        vector<int> dp0(N + 2), dp1(N + 2);
        for (int n = 1; n <= N; n++) {
            dp1[n] = max(dp0[n - 1], dp1[n - 1]) + Cnt(rd[n].first, vRight[n]);
            const int g = Cnt(vLeft[n], rd[n].first);
            dp0[n] = dp0[n - 1] + g;
            const int iRepeat = g + Cnt(rd[n - 1].first, vRight[n - 1]) - Cnt(rd[n - 1].first, rd[n].first);
            dp0[n] = max(dp0[n], dp1[n - 1] + g - max(0, iRepeat));
        }
        int cntSamePos = 0;
        for (const auto& pos : robots) {
            cntSamePos += Cnt(pos - 1, pos + 1);
        }
        return cntSamePos + max(dp0[N], dp1[N]);
    }
};