P8370 [POI 2001] Goldmine

题意：

你有

n

个坐标为

(x_i,y_i)

的点，以及一个

s\times w

的矩形区域，问这个区域最多能包含多少个点

解法：

扫描线模板题，与 P1502 窗口的星星这道题几乎一模一样。

扫描线算法核心思想：

用一条假想的直线（通常为垂直线）从左到右（或从上到下）扫过所有矩形。

将二维问题转化为一系列一维问题处理，关键在于处理扫描线与矩形边界的交点（事件点）。

在本题中就可以将点全部存其来，排序后去重就可以得到操作的区间，按照扫描线的方法打就好了

注意的点：

与窗口的星星不同之处在于 若矿石位于这块地的边缘，我们同样认为他是属于这个区域的，那么也就是说这里要 W++,H++。

code:

CPP

#include<bits/stdc++.h>
#define ll long long
#define ls(x) x<<1
#define rs(x) x<<1|1
#define N 100005
using namespace std;
struct NN{ll x,l,r,w;}q[N];
int T,n,W,H,t,cnt;
ll ans,a[N],lz[N],tr[N];
int cmp(NN a,NN b){return a.x==b.x?a.w>b.w:a.x<b.x;}
void pushup(int x){tr[x]=max(tr[ls(x)],tr[rs(x)]);}
void pushdown(int x){
	if(lz[x]){
		tr[ls(x)]+=lz[x],lz[ls(x)]+=lz[x];
		tr[rs(x)]+=lz[x],lz[rs(x)]+=lz[x],lz[x]=0;
	}
}
void update(int x,int l,int r,int L,int R,int w){
	if(L>R)return;
	if(l>=L&&r<=R){tr[x]+=w,lz[x]+=w;return;}
	int mid=(l+r)>>1;
	if(lz[x]) pushdown(x);
	if(R<=mid) update(ls(x),l,mid,L,R,w);
	else if(L>mid) update(rs(x),mid+1,r,L,R,w);
	else update(ls(x),l,mid,L,mid,w),update(rs(x),mid+1,r,mid+1,R,w);
	pushup(x);
}
int main(){
	scanf("%d%d%d",&W,&H,&n),W++,H++;
	for(ll i=1,x,y;i<=n;i++){
		scanf("%lld%lld",&x,&y);
		a[++t]=y,a[++t]=y+H-1;
		q[++cnt]={x,y,y+H-1,1},q[++cnt]={x+W-1,y,y+H-1,-1};
	}
	sort(a+1,a+t+1);
	t=unique(a+1,a+t+1)-(a+1);
	sort(q+1,q+cnt+1,cmp);
	for(int i=1;i<=cnt;i++){
		int l=lower_bound(a+1,a+t+1,q[i].l)-a;
		int r=lower_bound(a+1,a+t+1,q[i].r)-a;
		update(1,1,t,l,r,q[i].w);ans=max(ans,tr[1]);
	}
	printf("%lld",ans);
	return 0;
}

题解：P8370 [POI 2001] Goldmine

文章操作

P8370 [POI 2001] Goldmine

题意：

解法：

注意的点：

code:

相关推荐

评论

题解：P8370 [POI 2001] Goldmine