题解 P5867 【[SEERC2018]Fishermen】

VioletIsMyLove · 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;
}