P1298 最接近的分数

题解

之前在神秘模拟赛中见到的 \(trick\)，今天才发现就是 \(Stern-Brocot\) 树。

但是感觉用处可能没有那么大？算了，不管了。

类似二分，将左端点设为 \(\frac{a}{b}\)，右端点为 \(\frac{c}{d}\)。初始时 \(a=0,b=1,c=1,0\)。

我们要取一个类似中点的东西，我们会发现 \(\frac{a}{b} \leq \frac{a+c}{b+d} \leq \frac{c}{d}\)。

每次取这个东西当一个隔断点，判断和目标的精度，是修改左端点还是右端点。
即将区间变为 \([\frac{a}{b},\frac{a+c}{b+d}]\) 还是 \([\frac{a+c}{b+d},\frac{c}{d}]\)，这是一个类似树形的结构，并且每一个点的分数都是最简分数。

值得注意的是，时间复杂度最坏是 \(O(n)\) 的，可以构造数据卡掉。

虽然可以卡掉，但是这个树形结构的性质很优良，可以做到很多的事情。

这么判多解？就是搜索到精度足够的时候看看往下再走一层是不是还符合符合数据范围即可。