题解：P11512 [ROIR 2017 Day 2] 力场

algo_h · 2025-01-08 01:01:17 · 题解

以下两种思路不可行：

• 二分答案验证：需要判断给定的面积下限（二分中点）是否可以实现。由于无法确定每一个满足面积要求的矩形是否选取，不存在 O(n) 的方案。总复杂度不能做到 O(n\log n)。
• 三分法寻找最大值：假设当一个矩形的 x 长度满足 x \geq x_\mathrm m 时，我们将其选入候选集中。如果候选集的元素数目大于等于 k，则选中第 k 大的 y_k 坐标，计算 x_\mathrm my_k，得到约束 x \geq x_\mathrm m 下的最大公共面积 S(x_\mathrm m)；否则定义 S(x_\mathrm m) = 0。函数 S(x_\mathrm m) 是上凸函数，对其进行优化可以得到全局最优解。但其变化率可能在多处为 0，这导致三分法十分不便。

以上第二种不可行思路与本题的一种常规解法已经十分接近。可以在对矩形右上角坐标点 (x, y) 按照字典序从小到大排序后，利用数据流的第 k 大算法，从最后一个矩形（x 最大的矩形）开始，遍历至第一个矩形（x 最小的矩形），当遍历到的矩形数目积累至 k 时或超过 k 后，总可以选取公共矩形的横坐标为 x，并以 O(\log n) 的代价得到当前第 k 大的 y，统计 xy 的最大值即可得到答案。

以上过程存在选取的 x 不是最大公共矩形 x 的下确界的情况，但考虑相同的 y 第一次被取到的时候，那时候 x 必定是下确界，可以得到更大的 xy。故不是下确界的 x 对最终答案没有贡献，可以忽略。

#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int main()
{
  cin.tie(0)->sync_with_stdio(0);
  int n, k;
  cin >> n >> k;
  vector<pair<int, int>> p(n);  // 每个矩形右上角的点
  for(auto &xy : p) cin >> xy.first >> xy.second;
  sort(p.begin(), p.end());  // 按照先 x 后 y 的优先级排序

  long ans = 0;                                       // 最大公共面积
  priority_queue<int, vector<int>, greater<int>> pq;  // 大小不超过 k 的小顶堆
  for(int i = p.size() - 1; i >= 0; --i) {            // 计算/维护当前 x 下限要求的 y 的第 k 大值
    auto [x, y] = p[i];                               // 横坐标下降至 x，纵坐标新增 y
    if((int)pq.size() == k) {                         // 堆满
      if(pq.top() < y) pq.pop(), pq.push(y);          // 选择性置换
    } else {                                          // 堆不满
      pq.push(y);                                     // 插入 y
    }
    if((int)pq.size() == k) {              // 堆顶成为了序列流第 k 大
      ans = max(ans, (long)x * pq.top());  // 计算面积
    }
  }
  cout << ans << endl;
  return 0;
}