P1298

P1298 最接近的分数 题解 之前在神秘模拟赛中见到的 \(trick\)，今天才发现就是 \(Stern-Brocot\) 树。 但是感觉用处可能没有那么大？算了，不管了。 类似二分，将左端点设为 \(\frac{a}{b}\)，右端点为 \(\frac{c}{d}\)。初始时 \(a=0,b= ......

算是水紫，不过也学到一些有用的东西。 题意 给定正小数 $N$。求分子不大于 $n$，分母不大于 $m$ 的分数 $\dfrac{n}{m}$，使得 $\dfrac{n}{m}$ 的值与 $N$ 最接近（这里的最接近指的是 $|\dfrac{n}{m} - N|$ 最小）。 分析 首先，大部分人都可 ......