TCO SRM778 DIV1 KRECTANGLEINTERSECTION
题意
给 n 个矩形 (n<=200) 选 k 个矩形求他们的交的面积, 求最大面积
思路
一开始看错题写个扫描线过不了样例..
我们可以考虑在一维情况下的问题: 选取 k 个线段使得线段的交最大如何实现. 首先我们对于线段由左端点排序. 对于一个左端点 x 来说, 左端点小于等于它并且右端点大于等于它的所有线段, 我们为了方便记为多重集合 S, 我们按照右端点对 S 进行排序, 由于要取交, 假设你选择对应 x 的右端点 y 来说, 在集合 S 里面要选 k 个值是大于等于 y 的, 要求把 y 最大化, 如果最大化呢 只要取最大的 k 个里面最小的那一个就行了. 这样我们从左到右扫一遍, 维护一个大小为 k 的多重集合, 就把问题解决了.
那么对于该问题如何解决呢 , 我们可以看到 n 只有 200 , 那么我们可以枚举 x 轴的两点, 并且把包含这两点所有矩形 y 轴看做一维情况下的线段, 使用一维情况求得最长值, 乘以 x 轴枚举的两点的线段长度就是答案了.
注意: 枚举 x 轴左右端点我们可以直接分别枚举矩形的起点和终点, 因为 x 轴选取的线段一定是某个的起点和某个的终点, 因为是交, 所以矩形集合里面的最小 l 和最小 r 就是他们的范围, 所以一定一个是起点一个是终点.
细节: 维护队列的时候如果加入后超过了 k 个 要先删除一个, 再进行求 k 个线段交 例如存在 3 个 [1,10] 当枚举到 [3,9] 的时候 , 先把 9 加入队列再把它删除虽然代码计算了 [3,10], 但是这是没有意义的, 因为此时加入[3,9] 后队列中有 k+1 个元素并且 9 是队列里面的最小右端点 那么加入前的 k 个元素的交肯定包含了 [3,9] 肯定比 [3,9] 大, 至少是 [3, 未加入[3,9] 时候队列的最小值], 所以此时无意义, 为了统一性可以先加 9 再删 9, 但是严谨来说其实可以判一下 9 和队列里面的最小值比如此时是 10,9 比 10 小, 保留队列里面的 k 个是更优的, 所以不加入, 也不计算.
如果先删会带来什么后果 例如 3 个 [1,3] [1,3][1,100] 来了个[2,2] 把[1,3]顶掉了变成 [1,3][2,2][1,100] 这不就炸了吗..
- #include<bits/stdc++.h>
- using namespace std;
- struct KRectangleIntersection{
- long long maxIntersection(vector <int>xl, vector <int>yl, vector <int>xr, vector <int>yr, int k){
- long long ans=0;
- int n=yr.size();
- for(int st:xl){
- for(int ed:xr){
- if(st>=ed)continue;
- vector<pair<int,int>>y;
- for(int i=0;i<n;i++){
- if(xl[i]<=st&&xr[i]>=ed)y.push_back(make_pair(yl[i],yr[i]));
- }
- if((int)y.size()<k)continue;
- sort(y.begin(),y.end());
- priority_queue<int,vector<int>,greater<int>>q;
- int leny=0;
- for(int i=0;i<y.size();i++){
- q.push(y[i].second);
- if((int)q.size()>k)q.pop();
- if((int)q.size()==k){
- leny=max(leny,q.top()-y[i].first);
- }
- }
- ans=max(ans,1ll*(ed-st)*(leny));
- }
- }
- return ans;
- }
- };
来源: http://www.bubuko.com/infodetail-3449156.html