[BZOJ1604] [Usaco2008 Open]Cow Neighborhoods 奶牛的邻居（好题）

传送门

良心题解

#include <set> #include <cstdio> #include <iostream> #include <algorithm> #define N 100001 #define LL long long #define INF (~(1 << 31)) using namespace std; int n, c, h = 1, ans, ans1; int f[N], sum[N]; struct node }p[N]; multiset <node> s; multiset <node> :: iterator it; inline bool operator < (const node &a, const node &b) inline int read() inline int find(int x) inline int merge(int x, int y) } int main() sort(p + 1, p + n + 1); s.insert(node(INF, 0)); s.insert(node(INF, 0)); for(i = 1; i <= n; i++) y = p[i].y; it = s.lower_bound(node(p[i].y, i)); node r = *it, l = *it; if(r.x y <= c) merge(r.y, i); if(y l.x <= c) merge(l.y, i); s.insert(node(p[i].y, i)); } for(i = 1; i <= n; i++) sum[find(i)]++; for(i = 1; i <= n; i++) ans1 = max(ans1, sum[i]); printf("%d %d\n", ans, ans1); return 0; }

　　

上一篇：【模板】AC自动机

下一篇：[BZOJ1582] [Usaco2009 Hol]Holiday Painting 节日画画（线段树）

---

stl 并查集 好题