JOI 2015 FInal 舞会

题意

IOI 王国为了庆祝 JOI 公主的生日，举行了舞会。
预定有 $ N $ 位贵族要参加舞会。 $ N $ 是奇数。将贵族们从 $ 1 $ 到 $ N $ 编号。每个贵族有一个由整数表示的舞蹈熟练度 。贵族 $ i(1 \leq i \leq N) $ 舞蹈熟练度为 $ D_i $。
舞会中，含 JOI 公主在内的 $ N+1 $ 人两两一组跳舞。 IOI 王国遵循老手帮新手的传统，按以下方法决定跳舞的分组。

开始时， $ N $ 个贵族排成一列。
直到队列中只剩下一个贵族为止，不断进行以下操作。
调查最前面 $ 3 $ 个贵族的舞蹈熟练度。
这 $ 3 $ 个人中舞蹈熟练度最大的贵族称为 $ A $ 。如果存在多个人，从中选出序号最小的称为 $ A $ 。
这 $ 3 $ 个人中舞蹈熟练度最小的贵族称为 $ B $ 。如果存在多个人，从中选出序号最大的称为 $ B $ 。
$ A $ 和 $ B $ 离开队列并组成一组。
这三人中没有被选择的一个人移动到队列最后。
最后剩下的一个人和 JOI 公主一组。

从第 $ 1 $ 个贵族到第 $ M(1 \leq M \leq N-2) $ 个贵族的 $ M $ 个贵族已经决定了自己开始时排在队列的第几个。剩下的 $ N-M $ 个贵族的排列方式可以由国王自由决定。

因为 JOI 公主才刚开始学跳舞，国王想知道和 JOI 公主组队的贵族的舞蹈熟练度的最大值。

题解

很巧妙的一道题。

容易发现我们将一起操作的三个向一个新点连边，这是一颗三叉树的形状，相当于每个非子节点选择儿子节点的中位数来当作自己的权值。

我们想知道一个值能不能作为答案，发现这个东西只和相对的大小关系有没有关。

所以我们考虑枚举一个值 $x$ ，将数列中小于 $x$ 设为 $0$，反之设为 $1$。

发现我们这样不能判定使得根节点的值为 $x$ ，但是可以判断它是否为大于等于 $x$ 的某个数字，只需要判断根节点的值能否为 $1$ 即可，这样我们也能够知道答案一定是大于等于 $x$ 的。

发现我们判定了值之后可以缩小答案的范围，所以可以使用二分，找到最大的一个使得判定成立的一个。

判定十分简单，这个可以用 $dp$ 来解决，只需要设 $f_i$ 表示使 $i$ 为 $1$ 的最小需要添加的 $1$ 的个数即可，而这个节点要为 $1$ 则儿子节点至少 $2$ 个 $1$，知道了这个转移就十分简单了。

code

...

为什么说这题很巧妙呢。
我们其实可以发现答案是没有单调性的。
但是我们的判断可以判断一个后缀，这个后缀是有单调性的，所以我们实际上是在二分后缀。
发现答案没有单调性的时候不要马上抛弃二分，可以想一想判定的方式，固定一个东西之后我们能够判定什么。
同时在只关心大小关系的时候，$01$ 转化是常用的技巧，如：中位数。