首页 > 代码库 > BZOJ1604 [Usaco2008 Open]Cow Neighborhoods 奶牛的邻居
BZOJ1604 [Usaco2008 Open]Cow Neighborhoods 奶牛的邻居
BZOJ200题纪念！
一个非常巧妙的方法求曼哈顿距离：
如果原来坐标是(x, y)，令新的坐标为(X, Y), 其中X = x + y, Y = x - y
那么：曼哈顿距离 = |x1 - x2| + |y1 - y2| = max(|X1 - X2|, |Y1 - Y2|)
于是我们先进行坐标变换，按X排序。
然后用一个队列来做，满足队尾X - 队首X < c。
对这个队列中每个点的Y维护一棵平衡树，如果新加入元素的前驱后继与它的Y值差值不超过c，则用并查集将他们连在一起。
（其实就是类似kruskal的改进版本）
蒟蒻不会平衡树，于是又使用了STL的multiset。。。
1 /************************************************************** 2 Problem: 1604 3 User: rausen 4 Language: C++ 5 Result: Accepted 6 Time:868 ms 7 Memory:5396 kb 8 ****************************************************************/ 9 10 #include <cstdio>11 #include <algorithm>12 #include <set>13 14 using namespace std;15 typedef long long ll;16 const ll inf = (ll) 1e16;17 const int N = 100005;18 19 struct data{20 ll x, y;21 int w;22 }a[N];23 inline bool operator < (const data &a, const data &b){24 return a.y < b.y;25 }26 inline bool cmpx (const data &a, const data &b){27 return a.x < b.x;28 }29 30 int fa[N], cnt[N], ans, ANS;31 int n, c, X, Y;32 multiset <data> S;33 set <data> ::iterator it;34 35 int x;36 char ch;37 inline unsigned int read(){38 x = 0;39 ch = getchar();40 while (ch < ‘0‘ || ch > ‘9‘)41 ch = getchar();42 43 while (ch >= ‘0‘ && ch <= ‘9‘){44 x = x * 10 + ch - ‘0‘;45 ch = getchar();46 }47 return x;48 }49 50 int find_fa(int x){51 return fa[x] == x ? x : fa[x] = find_fa(fa[x]);52 }53 54 inline void Union(int x, int y){55 x = find_fa(x), y = find_fa(y);56 if (x != y)57 fa[x] = y, --ans;58 }59 60 void work(){61 for (int i = 1; i <= n; ++i)62 fa[i] = i;63 S.insert((data) {0, inf, 0});64 S.insert((data) {0, -inf, 0});65 S.insert(a[1]);66 int now = 1;67 data l, r;68 for (int i = 2; i <= n; ++i){69 while (a[i].x - a[now].x > c)70 S.erase(S.find(a[now++]));71 it = S.lower_bound(a[i]);72 r = *it, l = *--it;73 if (a[i].y - l.y <= c)74 Union(a[i].w, l.w);75 if (r.y - a[i].y <= c)76 Union(a[i].w, r.w);77 S.insert(a[i]);78 }79 }80 81 int main(){82 n = read(), c = read(), ans = n;83 for (int i = 1; i <= n; ++i){84 X = read(), Y = read();85 a[i].x = X + Y, a[i].y = X - Y, a[i].w = i;86 }87 sort(a + 1, a + n + 1, cmpx);88 89 work();90 for (int i = 1; i <= n; ++i)91 ++cnt[find_fa(i)];92 for (int i = 1; i <= n; ++i)93 ANS = max(ANS, cnt[i]);94 printf("%d %d\n", ans, ANS);95 return 0;96 }
BZOJ1604 [Usaco2008 Open]Cow Neighborhoods 奶牛的邻居
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。