自动搬运

查看原文

来自洛谷，原作者为

	VioletIsMyLove AFO

搬运于2025-08-24 22:15:05，当前版本为作者最后更新于2020-08-01 18:59:14，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

拿到这道题，我们的第一想法就是按照题目要求模拟，看每个渔夫能钓到哪些鱼，但这思路的时间复杂度是 $n^2$ ，我们就卡在这里了。

因为渔夫的位置是线性的，按照某种方式排序后，他们能钓到的鱼就会在一个区间内，但是对鱼该如何处理呢？按 $x+y<b.x+b.y$ 进行sort?显然这样是有反例的，因为鱼的x是要和渔夫的x进行加减处理的，但是既然想到这里，鱼要自带2个变量，而渔夫却只有一个！

逆向思维，不去想渔夫可以钓到哪些鱼，而是对于这条鱼，它能被哪些渔夫抓到！这样只要对渔夫按照位置从小到大排序，并记录其编号，然后二分啊，写2个二分，分别记录能抓住这条鱼最左边的渔夫和能抓住这条鱼最右边的渔夫，然后用扫描线，左端点+1，右端点往右推一个-1。

但会发现，渔夫的坐标是 $0$ 到 $1*10^9$，用扫描线的话会存不下，再读读题，渔夫的数量少啊，只有 $2*10^5$,对渔夫进行离散不就好啦？这题想到这里就已经没问题了。贴上代码。

Code:

#include<bits/stdc++.h>
using namespace std;
struct ZS{
	int x,y;
}a[200005];
struct zs{
	int x,id;
	bool operator <(const zs b)const{return x<b.x;}
}b[200005];
int n,m,l;
int c[200005],s[200005],ans[200005];
int find(int i){
	int L=1,R=m,mid,cnt=0;
	while(L<=R){
		mid=(R-L>>1)+L;
		if(abs(a[i].x-b[mid].x)+a[i].y<=l)cnt=mid,R=mid-1;
		else if(a[i].x<b[mid].x)R=mid-1;
		else L=mid+1;
	}
	return cnt;
}
int finds(int i){
	int L=1,R=m,mid,cnt=-1;
	while(L<=R){
		mid=(R-L>>1)+L;
		if(abs(a[i].x-b[mid].x)+a[i].y<=l)cnt=mid,L=mid+1;
		else if(b[mid].x<a[i].x)L=mid+1;
		else R=mid-1;
	}
	return cnt;
}
inline int read(){
	int ret=0,f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
	while(isdigit(ch)){ret=ret*10+ch-'0';ch=getchar();}
	return ret*f;
}
int main(){
	n=read();m=read();l=read();
	for(int i=1;i<=n;i++)a[i].x=read(),a[i].y=read();
	for(int i=1;i<=m;i++)b[i].id=i,b[i].x=read();
	sort(b+1,b+1+m);
	for(int i=1;i<=n;i++){
		int L=find(i),R=finds(i);
		c[L]++;c[R+1]--;
	}
	for(int i=1;i<=m;i++)s[i]=s[i-1]+c[i];
	for(int i=1;i<=m;i++)ans[b[i].id]=s[i];
	for(int i=1;i<=m;i++)printf("%d\n",ans[i]);
	return 0;
}