[BZOJ1594] [Usaco2008 Jan]猜数游戏（二分 + 并查集）

传送门

题中重要信息，每堆草的数量都不一样。

可以思考一下，什么情况下才会出现矛盾。

1.如果两个区间的最小值一样，但是这两个区间没有交集，那么就出现矛盾。

2.如果两个区间的最小值一样，并且这两个区间有交集，那么这个最小值一定在交集中，但是如果这个交集被某个最小值较大的区间，或是一些最小值较大的区间的并集包含，那么也是矛盾的。

可以二分答案，将这些区间按照最小值从大到小排序，然后可以用线段树维护，也可以用并查集来搞。

下面是用并查集来搞的。

每到一个区间，可以将[l,r]中的f变成r+1，如果发现find(l) > r那么说明这个区间已经被最小值较大的区间所包含。

#include <cstdio> #include <iostream> #include <algorithm> #define N 1000011 #define min(x, y) ((x) < (y) ? (x) : (y)) #define max(x, y) ((x) > (y) ? (x) : (y)) int n, q, ans; int f[N]; struct node p[N], t[N]; inline int read() inline bool cmp(node x, node y) inline int find(int x) inline bool check(int k) else } if(find(lmax) > rmin) return 1; return 0; } int main() printf("%d\n", ans); return 0; }

　　

上一篇：[BZOJ1589] [Usaco2008 Dec]Trick or Treat on the Farm 采集糖果（tarjan缩点 + 记忆化搜索）

下一篇：[BZOJ4992] [Usaco2017 Feb]Why Did the Cow Cross the Road（spfa）

---

二分 并查集