bzoj 1604: [Usaco2008 Open]Cow Neighborhoods 奶牛的邻居

Description

了解奶牛们的人都知道,奶牛喜欢成群结队.观察约翰的N(1≤N≤100000)只奶牛,你会发现她们已经结成了几个群.每只奶牛在吃草的时候有一个独一无二的位置坐标Xi,Yi(l≤Xi,Yi≤[1..10^9];Xi,Yi∈整数.当满足下列两个条件之一,两只奶牛i和j是属于同一个群的:
1.两只奶牛的曼哈顿距离不超过C(1≤C≤10^9),即lXi - xil+IYi - Yil≤C.
2.两只奶牛有共同的邻居.即,存在一只奶牛k,使i与k,j与k均同属一个群.
给出奶牛们的位置,请计算草原上有多少个牛群,以及最大的牛群里有多少奶牛

Input

第1行输入N和C,之后N行每行输入一只奶牛的坐标.

Output

仅一行,先输出牛群数,再输出最大牛群里的牛数,用空格隔开.

Sample Input

4 2
1 1
3 3
2 2
10 10

  • Line 1: A single line with a two space-separated integers: the

    number of cow neighborhoods and the size of the largest cow

    neighborhood.

Sample Output

2 3

OUTPUT DETAILS:

There are 2 neighborhoods, one formed by the first three cows and

the other being the last cow. The largest neighborhood therefore

has size 3.

Solution

每个点的坐标改为 x=x+y,y=xy ,这样条件就变成了 max(|x1x2|,|y1y2|)=c
于是将新坐标按x排序,从左往右扫,维护一个队列,其中的元素x坐标之差不超过c,然后每次新加一个点时考虑其y坐标在队列中的点的前驱与后继,如果y坐标之差不超过c则用并查集合并。

#include bits/stdc++.h

using namespace std;

const int MAXN = 100005;

int n, c;

struct Point{
    int x, y, id;
    Point() {}
    Point(int a, int b, int c) : x(a), y(b), id(c) {}
    bool operator  (const Point p) const {
        return x  p.x;
    }
};

int ans;
Point p[MAXN];
int fa[MAXN], cnt[MAXN];
multisetpairint, int  s;

int find(int p) {
    if (p == fa[p]) return p;
    return fa[p] = find(fa[p]);
}

void un(int a, int b) {
    int x = find(a), y = find(b);
    if (x != y) ans--;
    fa[x] = y;
}

int main() {
    scanf("%d %d", n, c);
    int a, b;
    for (int i = 1; i = n; i++) {
        scanf("%d %d", a, b);
        p[i] = Point(a + b, a - b, i);
    }
    sort(p + 1, p + n + 1);
    for (int i = 1; i = n; i++)
        fa[i] = i;
    ans = n;
    int l = 1;
    s.insert(make_pair(p[1].y, p[1].id));
    for (int i = 2; i = n; i++) {
        // cout  p[i].x  ' '  p[i].y  endl;
        while (l  i  p[i].x - p[l].x  c) {
            s.erase(s.find(make_pair(p[l].y, p[l].id)));
            l++;
        }
        setpairint, int ::iterator it = s.lower_bound(make_pair(p[i].y, p[i].id));
        if (it != s.end()  it - first - p[i].y = c) un(p[i].id, it - second);
        if (it != s.begin()  p[i].y - (--it) - first = c) un(p[i].id, it - second);
        s.insert(make_pair(p[i].y, p[i].id));
    }
    int ma = 0;
    for (int i = 1; i = n; i++) {
        cnt[find(i)]++;
        ma = max(ma, cnt[find(i)]);
    }
    printf("%d %d\n", ans, ma);
    return 0;
}
最新回复(0)
/jishuX1Tn2QzbsB5oC67V34KL1MnCyc4L6Vi_2BhSF4TYc18zg_3D4858336
8 简首页