Gym - 101964E Fishermen(差分区间修改)

Gym - 101964E  Fishermen(差分区间修改)

题目如上:

题意:题意:n条鱼,每条鱼有自己的坐标
有m个捕鱼人,每一个捕鱼人都给出x坐标(y坐标默认为0)
每一个捕鱼人都有一个范围 l ,在范围内都能捕鱼,距离为 |a-x|+b

问最后每个捕鱼人对应可以捕捉到多少条鱼

思路:

其实我们稍微思考以下就可以知道:看一下样例中给的图

Gym - 101964E  Fishermen(差分区间修改)

(1)我们会发现 l 以上的所有鱼都不可能被捕到。 ( fish.y > l ) 就不能捕到

(2)如果从捕鱼人的角度去看的话,我们可能需要两重循环,(对人和鱼都遍历)

但是如果计算鱼的贡献的话,我们可以通过计算找到图上 【L,R】 贡献范围,那么只需要对鱼遍历一次然后对区间内进行运算即可。

由于题目中给出的人在x轴的位置是随机的,所以还要先记录一次id顺序,最后在映射一次输出结果。

#include <bits/stdc++.h>
using namespace std;
typedef  long long ll;
const int maxn = 2e5+7;
struct fish
{
    int x,y;
}fishes[maxn];
struct fm
{
    int x,id;
    bool operator <(const fm &a)const 
    {
        return x<a.x;
    }
    
}fishmen[maxn];
int sum[maxn],ans[maxn];
int main(){
    int n,m,l;
    scanf("%d %d %d",&n,&m,&l);
    for (int i=1;i<=n;i++)
        scanf("%d %d",&fishes[i].x,&fishes[i].y);
    for (int i=1;i<=m;i++) {
        scanf("%d",&fishmen[i].x);
        fishmen[i].id=i;//输入的顺序 
    }
    sort(fishmen+1,fishmen+m+1);
    for (int i=1;i<=n;i++){
        if (fishes[i].y-l>0) continue;
        fm tmp;
        tmp.x=fishes[i].x-l+fishes[i].y;
        int L=lower_bound(fishmen+1,fishmen+m+1,tmp)-fishmen;
        tmp.x=fishes[i].x+l-fishes[i].y;
        int R=upper_bound(fishmen+1,fishmen+m+1,tmp)-fishmen;
        sum[L]++;
        sum[R]--;
    }
    for (int i=1;i<=m;i++){
        sum[i]+=sum[i-1];
        ans[fishmen[i].id]=sum[i];
    }
    for (int i=1;i<=m;i++) printf("%d\n",ans[i]);
    return 0;
}

 

上一篇:枚举SMB共享期间出错:没有启动国服务器服务 共享出问题了


下一篇:6081: Gym Class(拓扑排序+优先队列)