题目概述

著名盗贼 Bajtymon 计划抢劫博物馆，需要选择贿赂保安来最大化收益。
核心问题：选择一些保安进行贿赂，使得所有不在未被贿赂保安视野范围内的展品总价值，减去贿赂费用，最大化。

问题转化与建模

关键信息提取

• 有 $n$ 件展品，$m$ 名保安。
• 保安朝 $y$ 坐标减小方向看，视野半角正切值 $w/h$。
• 每件展品有位置 $(x_i, y_i)$ 和价值 $v_i$。
• 每名保安有位置 $(x_j, y_j)$ 和贿赂费用 $v_j$。
• 保安的视野是一个向下的无限长扇形（角度固定）。

几何建模

坐标变换

为了简化视野判断，题目提示使用线性变换：

设新坐标： [ u = x \cdot h + y \cdot w ] [ v = x \cdot h - y \cdot w ]

为什么这样变换？

• 在原始坐标系中，保安视野边界是两条斜率为 $\pm w/h$ 的直线。
• 变换后，视野变成水平向右的无限长条形区域（更易处理）。

视野条件

对于保安 $S$ 和展品 $E$：

• 在原始坐标系中，$E$ 在 $S$ 视野内当且仅当：
  • $y_E \le y_S$（在保安下方）
  • 且 $E$ 在两条边界线之间。
• 变换后，条件变为：
  • $u_E \ge u_S$ 且 $v_E \le v_S$（这里注意符号，取决于变换定义）

实际上，从代码可以看出：

• 排序按 $u$ 坐标升序，$v$ 坐标降序。
• 保安能看到的展品满足：$u_E \ge u_S$ 且 $v_E \le v_S$。

算法思路

核心思想

贪心 + 扫描线 + 集合维护

1. 将所有点（展品和保安）按 $u$ 坐标排序，$u$ 相同时保安优先（$v$ 降序）。
2. 扫描过程：
   • 遇到展品：加入候选集合（按 $v$ 坐标排序）。
   • 遇到保安：从候选集合中移除它能看到的展品（按 $v$ 坐标从小到大），直到贿赂费用用完或没有更多可见展品。
3. 最终收益 = 所有展品总价值 - 剩余未被移除的展品价值。

为什么这样正确？

• 我们按 $u$ 坐标扫描，保证处理保安时，所有 $u$ 坐标小于等于它的展品都已加入集合。
• 保安只能看到集合中 $v$ 坐标小于等于它的展品（按 $v$ 升序取）。
• 贪心选择：保安按扫描顺序处理，每次移除它能看到的展品（价值尽可能多）。

代码解析

#include <iostream>
#include <algorithm>
#include <array>
#include <set>
using namespace std;
using LL = long long;
const int N = 4e5 + 5;
LL n, m, w, h, s;
array<LL, 4> a[N];  // [u, v, value, type(0=展品,1=保安)]
set<pair<LL, LL>> k; // 存储候选展品 (v坐标, 价值)

int main() {
    cin >> n >> m >> w >> h;
    
    // 读入展品，计算总价值
    for (LL i = 1, x, y, v; i <= n; i++) {
        cin >> x >> y >> v;
        s += v;
        a[i] = {x * h + y * w, x * h - y * w, v, 0};
    }
    
    // 读入保安
    for (LL i = n + 1, x, y, v; i <= n + m; i++) {
        cin >> x >> y >> v;
        a[i] = {x * h + y * w, x * h - y * w, v, 1};
    }
    
    // 排序：按u坐标升序，u相同时按v坐标降序（保安优先）
    sort(a + 1, a + n + m + 1, [](auto x, auto y) {
        return x[0] < y[0] || (x[0] == y[0] && x[1] > y[1]);
    });
    
    // 扫描过程
    for (LL i = 1, d; i <= n + m; i++) {
        auto [u, v_coord, val, type] = a[i];
        
        if (type == 0) { // 展品：加入候选集合
            k.insert({v_coord, val});
        } else { // 保安：移除它能看到的展品
            auto it = k.lower_bound({v_coord, 0});
            while (it != k.end() && val > 0) {
                auto [v_pos, value] = *it;
                it = k.erase(it);
                d = min(val, value);
                val -= d;
                s -= d; // 从总价值中减去被移除的展品价值
                if (value > d) { // 如果展品未被完全移除，放回剩余部分
                    k.insert({v_pos, value - d});
                }
            }
        }
    }
    
    cout << s; // 输出剩余展品总价值（即最大收益）
    return 0;
}

复杂度分析

• 时间复杂度：$O((n+m)\log(n+m))$
  • 排序：$O((n+m)\log(n+m))$
  • 扫描过程：每个展品最多被插入/删除一次，set 操作 $O(\log n)$
• 空间复杂度：$O(n+m)$

样例验证

以题目样例为例：

• 总展品价值：$2+3+8+4+1=18$
• 贿赂保安费用：$3+5+6$
• 最优方案：贿赂费用 $3+6=9$，获得展品价值 $2+8+4+1=15$
• 利润：$15-9=6$，与输出一致

算法通过扫描和贪心移除，模拟了保安视野覆盖展品的过程，最终得到最大利润。

总结

本题的难点在于：

1. 几何条件转化：将扇形视野转化为矩形查询。
2. 扫描线贪心：通过排序和集合维护，高效模拟覆盖过程。
3. 离散化思维：将连续几何问题转化为离散事件处理。

这种"坐标变换 + 扫描线 + 数据结构维护"的思路，在计算几何类题目中非常常见且有效。