题目解析

问题理解

我们需要从 N 个梨子中选出一个子集，使得选出的梨子数量最多，同时满足约束条件：

对于选出的梨子，设两个属性的最小值为 $A_0$ 和 $B_0$，则所有被选梨子 $i$ 都要满足：

$$C_1(A_i - A_0) + C_2(B_i - B_0) \leq C_3$$

核心思路：数学变形与维度分解

第一步：化简约束条件

将原不等式进行移项变形：

$$C_1 A_i + C_2 B_i \leq C_3 + C_1 A_0 + C_2 B_0$$

令 $V_i = C_1 A_i + C_2 B_i$（每个梨子的综合权值），则约束条件变为：

$$V_i \leq \text{Threshold}$$

其中 $\text{Threshold} = C_3 + C_1 A_0 + C_2 B_0$。

关键观察：一旦确定了 $A_0$ 和 $B_0$，问题就转化为统计有多少个梨子满足：

• $A_i \geq A_0$ 且 $B_i \geq B_0$（保证 $A_0, B_0$ 确实是最小值）
• $V_i \leq \text{Threshold}$（满足约束条件）

第二步：降维 - 固定一个维度

由于直接枚举所有可能的 $(A_0, B_0)$ 对会导致 $O(N^3)$ 复杂度，我们采用排序 + 枚举的策略：

1. 将所有梨子按 $A$ 值从小到大排序
2. 枚举第 $i$ 个梨子作为 $A_0$（即 $A_0 = A_i$）
3. 此时候选梨子只能从下标 $j \geq i$ 中选择（保证 $A_j \geq A_0$）

现在问题简化为：在确定的候选集合中，如何选择最优的 $B_0$？

第三步：动态维护的核心矛盾

对候选梨子按 $B$ 值排序，然后枚举每个梨子作为 $B_0$。关键观察：

当 $B_0$ 增大时，会产生两个相反的效果：

• 正面效果：$\text{Threshold}$ 增大 → 更多梨子可能满足 $V_i \leq \text{Threshold}$
• 负面效果：候选池缩小 → 必须满足 $B_i \geq B_0$ 的梨子减少

我们需要维护一个数据结构，支持：

1. 查询：当前有多少梨子的 $V$ 值 ≤ 当前门槛
2. 删除：移除不再满足 $B_i \geq B_0$ 的梨子

算法实现方案

方案一：树状数组（BIT）

核心思想：用 BIT 维护 $V$ 值的分布情况

实现细节：

• 预处理：计算所有 $V_i$ 并进行离散化
• 外层循环：枚举 $A_0$
• 内层循环：按 $B$ 排序后枚举 $B_0$
• 维护操作：
  • 查询：query(threshold_rank) - 统计 ≤ 门槛的梨子数
  • 删除：add(v_rank, -1) - 从 BIT 中移除当前梨子

关键技巧：离散化后查询门槛值时，需要找到 ≤ 门槛的最大离散值的排名

方案二：优先队列（堆）

核心思想：将梨子分为"达标"和"待定"两个集合

实现细节：

• 维护两个状态：
  • count：已达标的梨子数量
  • heap：存储暂时不达标（$V_i >$ 当前门槛）的梨子
• 门槛提高时：检查堆顶，将达标的梨子从堆中移出，count++
• 删除操作：使用懒惰删除策略
  • 如果梨子在达标集合中：直接 count--
  • 如果梨子在堆中：标记删除，等其成为堆顶时再实际删除

优势：无需离散化，思路直观

算法复杂度

两种方案的时间复杂度都是 $O(N^2 \log N)$：

• 外层循环：$O(N)$
• 内层循环：$O(N)$
• 每次操作：$O(\log N)$（BIT操作或堆操作）

总结

这道题的精髓在于：

1. 数学变形：将复杂约束条件转化为易于处理的形式
2. 维度分解：通过排序固定一个维度，降低问题复杂度
3. 动态维护：利用数据结构高效处理"门槛提升"与"候选缩减"的矛盾

两种解法各有特点：BIT 解法逻辑统一但需要离散化；堆解法更加直观但需要处理懒惰删除。掌握这两种思路有助于解决类似的动态统计问题。

代码