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

以下两种思路不可行：

二分答案验证：需要判断给定的面积下限（二分中点）是否可以实现。由于无法确定每一个满足面积要求的矩形是否选取，不存在 $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;
}

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

文章操作

相关推荐

评论

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