[BZOJ1604] [Usaco2008 Open] Cow Neighborhoods 奶牛的邻居 (queue & set)

时间：2025-01-29 21:37:14

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.

HINT

Source

　　Gold

Solution

　　设点$(x',y')$表示$(x+y,x-y)$，则：

　　有这样一个性质：两个点的曼哈顿距离为$max(|x'_1-x'_2|,|y'_1-y'_2|)$

　　所以先将所有点预处理，之后按$x'$坐标排序。

　　用一个队列维护$x'$使队列里所有元素$x'$之差不超过$C$，用set维护$y'$

　　若新插入元素的前驱或后继与该元素之差小于等于$C$就用并查集把它们连起来

　　数一下联通块的个数就行了。

 #include <bits/stdc++.h>

 #define fir first

 #define sec second

 #define mp make_pair

 using namespace std;

 typedef pair<int, int> pii;

 const int INF = ;

 set<pii> S;

 set<pii>::iterator it;

 queue<int> Q;

 pii a[];

 int fa[], siz[];

 int getfa(int x)

 {

     return fa[x] = x == fa[x] ? x : getfa(fa[x]);

 }

 int main()

 {

     int n, c, u, v, cnt = , mx = ;

     cin >> n >> c;

     for(int i = ; i <= n; i++)

     {

         cin >> a[i].fir >> a[i].sec;

         a[i].fir += a[i].sec;

         a[i].sec = a[i].fir -  * a[i].sec;

         fa[i] = i;

     }

     sort(a + , a + n + );

     S.insert(mp(-INF, )), S.insert(mp(INF, ));

     Q.push(), S.insert(mp(a[].sec, ));

     for(int i = ; i <= n; i++)

     {

         while(!Q.empty() && a[i].fir - a[Q.front()].fir > c)

         {

             u = Q.front(), Q.pop();

             S.erase(mp(a[u].sec, u));

         }

         it = S.lower_bound(mp(a[i].sec, ));

         if(it->sec && it->fir - a[i].sec <= c)

         {

             u = getfa(it->sec), v = getfa(i);

             if(u != v) fa[u] = v;

         }

         if((--it)->sec && a[i].sec - it->fir <= c)

         {

             u = getfa(it->sec), v = getfa(i);

             if(u != v) fa[u] = v;

         }

         Q.push(i), S.insert(mp(a[i].sec, i));

     }

     for(int i = ; i <= n; i++)

     {

         if(++siz[getfa(i)] == ) cnt++;

         mx = max(mx, siz[getfa(i)]);

     }

     cout << cnt << ' ' << mx << endl;

     return ;

 }

相关文章