外话

比赛时思考许久，赛后一看，求的是面积交，不是面积并，同时一百分。

正题

1.性质

\ \ \ \ \ \

观察样例可以发现，面积并实际上是

min(x_i)*min(y_i)

。

2.思路

\ \ \ \ \ \

根据这个性质，我们可以将

x

从大到小排序，以此枚举

min(x_i)

。这时，只有

x\ge min(x_i)

的矩形才能选，然后在这些矩形中选前

k

大的

y

（此时的

min(y_i)

就是第

k

大的

y

）。这时问题已经转化为动态维护第

k

大。

3.维护方法

\ \ \ \ \ \

用一个小根堆，先将前

k

个数插进去，插入一个数时直接

push

进小根堆，再把此时的最小值删去，这时的堆顶就是第

k

小。

4.代码

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=200005;
struct node{
	int x,y;
} a[N];
bool cmp(node a,node b){
	return a.x>b.x;
}
priority_queue<int,vector<int>,greater<int> > q;
signed main(){
	int n,k;
	cin>>n>>k;
	for(int i=1;i<=n;i++) cin>>a[i].x>>a[i].y;
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=k;i++) q.push(a[i].y);//前k个数入堆
	int ans=a[k].x*q.top();
	for(int i=k+1;i<=n;i++){//枚举min(xi)
		q.push(a[i].y);
		q.pop();
		ans=max(ans,a[i].x*q.top());//累计答案
	}
	cout<<ans;
    return 0;
}

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

文章操作

外话

正题

1.性质

2.思路

3.维护方法

4.代码

相关推荐

评论

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