摸鱼带师

Posted on Edited on In

题目大意:给你一个二维平面,然后有一些点随机落在上面,给定一些贴在x轴上的点,给定一个距离l为一个点若能看到周围点的话必须在l内(曼哈顿距离),问每个点可以看到多少个点

考场思路几近正解但是由于状态心态身体等各种原因,没能复现

现重新屡一下思路:

求解每个x轴上的选定点可以看到多少点,可以转化思维,考虑每一个平面上的一个点对x轴上的点的贡献,然后对下标差分答案就行了

代码如下: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <bits/stdc++.h>
#define int long long
#define ll long long
using namespace std;

const int N = 2e5 + 66;

int n, m, l;
int x[N], y[N];

struct yhzhyhm
{
    int a, id, res;
//constructor
    yhzhyhm (int A = 0) : a(A) {}
    bool operator < (const yhzhyhm &yhm) const {return a < yhm.a;}
}yh[N];

inline int cmp(yhzhyhm X, yhzhyhm Y)
{
    return X.id < Y.id;
}

signed main()
{
    int i; n = read(), m = read(), l = read();
    for (i = 1; i <= n; ++ i) x[i] = read(), y[i] = read();
    for (i = 1; i <= m; ++ i) yh[i].a = read(), yh[i].id = i;
    sort(yh + 1, yh + 1 + m);

    for (i = 1; i <= n; ++ i)
    {
        if (y[i] > l) continue;
        int lx = x[i] - (l - y[i]), rx = x[i] + (l - y[i]);
        int lp = lower_bound(yh + 1, yh + 1 + m, yhzhyhm(lx)) - yh,
            rp = upper_bound(yh + 1, yh + 1 + m, yhzhyhm(rx)) - yh;
        ++ yh[lp].res, -- yh[rp].res;
    }

    for (i = 2; i <= m; ++ i) yh[i].res += yh[i - 1].res;
    sort(yh + 1, yh + 1 + m, cmp);
    for (i = 1; i <= m; ++ i) put(yh[i].res);

    return 0;
}