这道题我在题库里刷到的时候标签写着“二分查找”难度普及题面名字却叫“分数排序”。第一眼感觉就是个排序题——把所有分数排个序输出第 k 个不就行了但真去枚举所有分数排序数据一大就完蛋。后来想明白这题的“二分查找”不是让你在数组里折半找数而是二分答案把“第 k 小”变成“有多少个分数小于 x”的计数问题。如果你正在学二分答案或者对这种“求第 k 小”的题目总是一筹莫展这篇记录值得你耐心看完。我尽量把判断依据、双指针原理、浮点二分精度这些坑全部讲透讲完你再去写代码会顺手很多。1. 一眼以为是排序题后来发现是二分答案的考场判断1.1 题目在讲什么分数配对的第 k 小先说题意。题目给出 n 个正整数让你任选两个位置组成分数 a[i] / a[j]有的版本允许 i 和 j 相同有的版本不允许但都是同一套做法。这样会产生 n² 个分数或者 n(n-1) 个要求把这些分数从小到大排序之后输出第 k 小的那个。光听描述很容易上头把所有分数枚举出来排序一下复杂度 O(n² log n)听起来很暴力但题目考的就是你能否看出这个操作不可行。拿小数据举例假设数组是 [1,2,3]所有配对分数是 1/1、1/2、1/3、2/1、2/2、2/3、3/1、3/2、3/3排序后很容易找到指定位置。可一旦 n 到了 10⁵ 级别n² 就是 10¹⁰先不说排序光是枚举这些分数内存就爆炸。更要命的是分数还会有重复值比如 1/2 和 2/4 在数值上相等“第 k 小”必须把并列的相同值都算进去。你没法只找到“一个”分数就完事必须知道有多少个分数严格小于它有多少个等于它。这个细节是很多初学者第一次交上去 WA 的根本原因。所以这道题从数据范围到重复值的处理处处都在暗示一件事不能真的把分数全部生成出来排序应该换一个思路。只有当你在考场上意识到“排序这条路走不通”才有机会看到题面里那个“二分查找”标签到底想让你干什么。这一步的思维转换比后面所有代码都重要。1.2 暴力排序为什么会被卡住我们来把暴力的代价算清楚。枚举所有配对是 O(n²)排序是 O(n² log n)空间也是 O(n²)。当 n2000 时4×10⁶ 个分数排序勉强能跑但 n10⁵ 时10¹⁰ 个分数这已经不是一个“优化常数”能解决的问题而是算法复杂度等级的差距。有人会说那我不排序用优先队列每次取最小值维护到第 k 个就停止是不是复杂度好一点如果 k 不大比如 k1000理论上是可行的。但题目的 k 往往逼近 n²优先队列照样要对堆里所有元素操作而且你还是得先把所有配对生成出来。所以这条路也被堵死。暴力的瓶颈在于“枚举”和“排序”是绑定的只要你想得到第 k 小就会天然地想把这些候选值组织成有序结构。二分答案的高明之处在于它把“排序整个集合”这件难事换成了“判断某个数是否过大”这件容易重复做的事。排序做一次要花 O(m log m)而二分判断只需要 O(log C) 次计数每次计数如果有双指针优化代价就降到了 O(n)。这个替换不是技巧性的取巧而是这一类“第 k 小”问题的通用解。只要你想通“我不需要真的知道所有分数的完整顺序只需要定位出‘刚好有 k 个分数小于它’的那个值”题目就已经破了一半。1.3 从“直接求值”换到“判断答案”这个转换是题眼“二分答案”和普通的“二分查找”不是一个概念。普通二分是在有序数组里找元素下标是离散的二分答案是猜一个连续值域里的数然后用判定函数告诉你“猜大了”还是“猜小了”。本题猜的是一个分数值 x判定函数是“有多少个配对分数小于 x”。这个转换有一个必然逻辑如果 count(x) k说明第 k 小的分数一定大于 x答案在下半区间如果 count(x) ≥ k说明 x 可能是答案或者答案比 x 小答案在上半区间。因为你把整个值域不断折半最后逼近的位置就是第 k 小分数的精确值。很多初学者卡在这一步是因为觉得“判定了半天还是不知道具体是哪两个下标组成的分数”。没必要知道。题目只要求输出这个数值又不是让你输出分子分母。只要二分收敛到了正确的值你就赢了。哪怕题目要求输出分数形式也可以在二分结束后通过一轮扫描收集候选分数这属于输出阶段的补充操作不影响主算法。所以真正的题眼只有一句话问题能不能转化为“给定 x快速统计出满足 a[i]/a[j] x 的配对个数”能转过去二分答案就成立转不过去二分答案就是空谈。下面两节一节解释为什么二分一定合法另一节解释计数函数怎么写得快。2. 二分答案的合法性单调性从哪冒出来的2.1 把第 k 小问题看成计数问题二分答案能被使用的首要条件是单调性。定义函数 count(x) 满足 a[i]/a[j] x 的配对数量。当 x 增大时这个数量只可能不变或者变大绝不可能是变小因为“小于一个更大数”的集合一定会包含“小于一个更小数”的集合。于是“第 k 小值是多少”就变成了“满足 count(x) ≥ k 的最小 x 是多少”。为什么是“最小”因为分数值可能有重复。比如有 3 个分数都等于 0.5k2那第 2 小就是 0.5。count(0.5) 只算了严格小于 0.5 的配对可能只有 1 个小于 2但 count(0.5ε) 一下子把 3 个 0.5 全算进去变成 4大于等于 2。所以二分逼近的目标是那个“刚刚好跨过 k 的门槛”的值也就是第 k 小分数本身。用生活例子理解想象一个活动室门口写着身高门槛门槛设得越低能进去的人越少。你在找“第 k 个被放行的人”对应的门槛高度。直接把所有人按身高排队当然可以但如果你知道“身高低于 h 的人数”就能通过不断调 h 逼近目标。这和本题完全同构只是人数变成了配对分数身高变成了分数数值。单调性的存在让二分不再依赖集合本身是否有序而是依赖一个“可重复计算”的计数函数。你不需要把所有数据组织成有序结构只要每次能用高效率算出 count(x)二分就能在这里生根。2.2 上界、下界与迭代次数的选择写二分答案边界不能随便设。下界我建议取排序后 a[0] / a[n-1]这是所有配对里可能出现的最小比值上界取 a[n-1] / a[0]这是最大比值。不要拍脑袋写成 0 到 1e18虽然大部分时候也能跑对但边界范围越大浮点误差带来的影响越难控制。排序只需要做一次。因为 a[i] 和 a[j] 是同一个数组里的元素排序后首尾元素直接给出最小和最大分数的原子值。如果你读到的版本是两个数组 A[i]/B[j]那就分别排序下界用 A[0]/B.back()上界用 A.back()/B[0]逻辑完全一致。迭代次数不要用 while (hi - lo eps)。这是很多选手踩过无数次的坑eps 设成 1e-9如果答案本身是 1e18double 的机器精度根本到不了 1e-9程序要么死循环要么精度不足直接 WA如果 eps 设大答案精度又不够。竞赛里稳妥做法是固定迭代 60 次每次把区间折半60 次之后区间宽度已经变成初始宽度的 2⁻⁶⁰大约 10⁻¹⁸远小于任何常见输出精度要求。万一担心极端数据迭代 80 次也没关系反正 count 函数是 O(n)多迭代一二十次对性能影响可以忽略。固定次数的另一个好处是耗时可控。如果你用 while 判断精度不同数据下循环次数会波动极端时可能超时。二分答案题里“数循环次数”比“量精度误差”更加可靠。这是我在多次实测里得到的经验建议你也直接采用这个习惯。2.3 浮点误差在二分里的位置为什么固定 60 次比判断精度稳浮点数在二分答案里最容易出问题的场景是“重叠判定”。比如一组数据里既有极大值也有极小值mid 和中位数同时很大时mid * a[j] 的乘积可能超过 double 的安全精确范围。C 的 double 能精确保存大约 2⁵³ 量级的整数如果乘积到了 10¹⁸ 数量级double 的舍入误差就开始变得肉眼可见。所以我在代码里统一用 long double 来存二分变量和做乘法比较。long double 在不同编译器下精度不一定相同但通常比 double 多出不少有效位配合 80 次迭代基本能覆盖绝大多数题目。有的题解喜欢用 long double 判断 while(hi-lo1e-18)这种做法虽然实际也能过但逻辑上没有固定次数那么干净。固定次数把“精度问题”变成了“次数够不够”的问题而 60 次对任何数据都是足够多的。还有一点二分结束时输出 hi 还是 lo在浮点误差下会有极小差别。我习惯输出 hi或者 (lo hi) / 2。二者差别通常在输出精度之外不必太纠结但别输出 lo 后又在特殊数据上偏小一截这种问题排查起来很费时间。更稳的做法是最后统一输出 hi因为 hi 始终是“满足 count(x) ≥ k 的当前上界”不会低于真实答案。3. 统计小于 mid 的分数个数排序一次双指针滑过去3.1 先把 a 排好序双指针才能动计数函数是本体的核心写不好前面的二分全白搭。最朴素的计数方法是枚举分母 a[j]然后在数组里二分查找第一个 mid * a[j] 的分子位置累积位置就是满足条件的分子个数。这样做一次计数的复杂度是 O(n log n)外面再套 60 次二分总复杂度是 O(60 n log n)。当 n2×10⁵ 时60×2×10⁵×18大概 2 亿次操作常数稍大可能卡线。双指针的目标就是把单次计数从 O(n log n) 砍到 O(n)。但双指针有前提数组必须有序。你要先对 a 做一次 sort排序只用做一次之后 60 次计数全部复用这个有序数组。这个一次排序的成本摊到整个二分过程里非常划算。有些人会问分母的顺序变了会不会破坏“配对”含义不会。题目只关心数值不关心原始位置。排序后我们用“排序位置”代替“原始下标”计数的是两个元素的数值组合和位置无关。哪怕题目要求下标不能相同我们也只是增加一个“跳过自配对”的修正排序本身不影响正确性。3.2 为什么指针可以只朝一个方向走双指针能成立的关键在单调性推导。数组 a 升序后随着分母位置 j 从小到大a[j] 单调不减。对固定的二分值 mid阈值 mid * a[j] 也随 j 单调不减。而分子这边满足 a[i] threshold 的位置一定也是单调右移的因为阈值变大能小于它的元素只会更多。于是可以用一个 pos 指针从 0 开始每次循环 j 后pos 不断向右移动直到 a[pos] mid * a[j] 或者 pos 到达 n。此时前 pos 个分子都能和当前分母构成小于 mid 的分数直接累加 pos。pos 在整轮计数里最多从 0 走到 n不会回退内层 while 的总移动次数是 O(n)外层 j 循环 O(n)整体 O(n)。复杂度均摊是理解这个算法的关键。内层 while 看起来是嵌套循环但 pos 只增不减所以所有内层操作加起来不超过 n 次和 j 循环无关。如果你把 pos 的初值写成每次从 0 开始那复杂度就退回 O(n²)这就是所谓“看似双指针实则暴力”的常见错误。一个容易绕晕的细节mid 是外层二分传进来的固定值每次 countLess 里它不变。阈值单调性只说 a[j] 在变并不依赖 mid 的变化。所以即使 mid 很大或很小pos 也不会回退。比如 mid 特别大第一个 j 就让 pos 冲到了 n之后所有 j 循环内层 while 都不会动计数每次直接加 n也没问题。3.3 如果题目要求下标不能重复计数要减哪里如果题面规定 i 和 j 必须来自不同位置计数代码不能简单地写 cnt pos。因为当前分母排序位置是 j而 pos 表示满足条件的分子有 pos 个位置覆盖 0 到 pos-1。如果 j pos说明分母自己也在可选的分子集合里a[j]/a[j] 这个自配对就会被误算进去需要减掉 1如果 j pos则分子集合里没有分母自己不用减。写成代码就是if (pos j) cnt pos - 1; else cnt pos;这个 1 的修正看似简单但非常容易漏。漏掉之后n1 时逻辑立刻出错数组只有一个元素正确答案应该是 0 个有效配对如果题目要求不同下标但朴素累加会得到 1。我就是在这里栽过跟头后来干脆把两种版本的题意分开封装用注释提醒自己。如果题目给的是两个数组 A 和 B求 A[i]/B[j]不存在“同一个元素自己配对”的问题双指针直接每次 cnt pos反而最干净。所以看到题面时要先确认是一数组还是双数组别把自配对的修正逻辑生搬硬套。4. 我的实现与调试记录整数比较还是浮点比较4.1 完整代码C二分双指针我把我实际能过测试数据的代码贴出来这里默认允许相同下标配对如果你手里的题面要求不同下标把注释那行换进去即可。#include bits/stdc.h using namespace std; typedef long long ll; int n; ll k; vectorll a; long long countLess(long double x) { int pos 0; long long cnt 0; for (int j 0; j n; j) { long double threshold x * (long double)a[j]; while (pos n (long double)a[pos] threshold) pos; cnt pos; // 允许 ij // 不允许 ij: // if (pos j) cnt pos - 1; // else cnt pos; } return cnt; } int main() { scanf(%d%lld, n, k); a.resize(n); for (int i 0; i n; i) scanf(%lld, a[i]); sort(a.begin(), a.end()); long double lo (long double)a[0] / a.back(); long double hi (long double)a.back() / a[0]; for (int t 0; t 60; t) { long double mid (lo hi) / 2.0L; if (countLess(mid) k) hi mid; else lo mid; } printf(%.12Lf\n, hi); return 0; }注意 k 必须用 long long因为 n10⁵ 时 n²10¹⁰ 已经溢出 int。a 也用 long long 存防止读入数据本身超过 int 范围。二分变量统一用 long double比较也全部转成 long double不要混用 double 和 long double否则编译器悄悄降精度。countLess 里的 threshold 每次用 x * a[j]这里 x 是 long doublea[j] 是 long long乘法会发生隐式提升但我还是显式写了 (long double)a[j]提醒自己和读者这个位置的数值类型有多敏感。如果不做提升某些编译器可能因为默认类型转换把乘积变成 double在乘积接近 10¹⁸ 时产生误差。4.2 溢出与精度mid*a[j] 别写成 int我第一次写这道题的时候把 mid 定义成 doublea[i] 定义成 int然后直接写 a[pos] mid * a[j]。当时小数据全对一上大数据 WA 到怀疑人生。排查了很久才发现mid * a[j] 的结果在 C 表达式里是 double 没错但如果 a[j] 本身是 int 且数值接近 1e9mid 再接近 1e9乘积就是 1e18double 在 1e18 附近的绝对误差会达到几百甚至几千计数函数边界乱跳。这类问题真的只能靠类型提升解决乘法双方至少一方是 long double或者统一强转。代码里 a[pos] 也要强转成 long double 再和 threshold 比否则左侧是 long long右侧是 long double虽然比较也能通过隐式转换但总是显式写更踏实。顺带一提如果你使用的是某些老式在线评测环境scanf 对 long double 的格式符要写成 %Lf打印用 %Lf 或者 cout 直接输出。不同编译器对 long double 的实现宽度不同但至少比 double 大这是我们选它的理由。4.3 实测性能与边界数据用几个小数据验证算法逻辑。数组 [2,4]n2允许自配对配对分数为 2/40.5、2/21、4/41、4/22。k1 答案 0.5k2 答案 1因为 0.5 一个等于 1 的有两个第二个就是 1k4 答案 2。跑二分countLess(1) 只算严格小于 1 的分数只有一个 0.5所以 countLess(1)1 2二分会把答案逼到 1 的上方最终输出 1.000000000000符合预期。再测全部相同值比如 [7,7,7]所有分数都是 1不管 k 是几答案都是 1。因为 countLess(0.999999999) 为 0countLess(1.000000001) 为 9二分会快速收敛到 1。大数据性能方面n10⁵排序 O(n log n)60 次 countLess 每次 O(n)总共约 6×10⁶ 次循环加上内层 pos 移动也是 6×10⁶ 量级轻松在 1 秒内跑完。这个复杂度结构很健康排序多一点二分计数线性不会出现某个阶段突然爆表。4.4 扩展如果题目要求输出最简分数怎么办有些变体题不让你输出浮点而是要求输出“分子/分母”的最简分数形式。这时候浮点二分只能帮你定位答案范围不能告诉你具体是哪两个成分。我的做法是二分结束后得到很窄的区间 [lo, hi]答案必落其中然后枚举分母 a[j]用二分找出所有满足 lo a[i]/a[j] hi 的分子位置把这些分数收集起来再统计小于 lo 的个数 cntBefore countLess(lo)对候选分数排序取第 k - cntBefore 个最后约分输出。候选排序不能用 double 直接比因为两个不同分数可能差小于浮点精度。用交叉相乘也就是比较 a[i1] * a[j2] 和 a[i2] * a[j1]这需要用到 __int128 防止中间乘积溢出GCC 环境基本都支持。示意代码如下// 假设已经完成 60 次二分lo 和 hi 是极窄区间 vectorpairll,ll cand; long double eps 1e-12L; for (int j 0; j n; j) { ll lowM (ll)ceil(lo * a[j] - eps); ll highM (ll)floor(hi * a[j] eps); lowM max(lowM, 1LL); int p lower_bound(a.begin(), a.end(), lowM) - a.begin(); int q upper_bound(a.begin(), a.end(), highM) - a.begin(); for (int i p; i q; i) cand.push_back({a[i], a[j]}); } sort(cand.begin(), cand.end(), [](auto x, auto y) { return (__int128)x.first * y.second (__int128)y.first * x.second; }); long long before countLess(lo); auto ans cand[k - before - 1]; ll g __gcd(ans.first, ans.second); printf(%lld/%lld\n, ans.first / g, ans.second / g);这个扩展不是题目必需但理解了之后你对“浮点二分定位 局部精确收集”的组合会更有感觉。遇到输出格式奇怪的变体题也不至于卡死在最后一步。5. 这道题真正想教你的一件事偏序计数套路5.1 第 k 小分数、第 k 小乘积、第 k 小点对都是一个形状把 P10091 的壳子剥掉剩下的骨架是给定两类元素定义组合指标 F(i,j)求所有 F 的第 k 小。做法永远是“二分答案 x 统计 F(i,j) x 的数量”。这个骨架可以套进很多看似无关的题。比如求两个数组乘积的第 k 小把 A、B 排序固定 A[i]在 B 上移动指针累计满足乘积小于 x 的数量同样是双指针。再比如求两数之和的第 k 小排序后固定左端点右端点随阈值单调移动。代码结构和本题几乎一样只是阈值表达式从除法变成乘法、加法。这就是“分数排序”真正值钱的地方它把所有必要的细节——单调性分析、计数函数设计、浮点技巧、边界判断——全部压缩在一个普及级别的题里。你做透这一道再去刷其他“第 k 小”题会感觉读题速度明显提升。5.2 什么时候别用这个套路一眼看出数据范围的取舍二分答案虽好但不是万能。如果 n 很小比如 n≤2000枚举所有配对排序反而更简单代码也更不容易错如果 k 很小可以用优先队列每次弹出当前最小值维护前 k 个小元素如果计数函数优化不到 O(n log n) 以内二分答案的 60 次倍数会让总复杂度变得无法承受。判断方法很简单先看 n² 的量级再看 k 的量级最后看题面允许的复杂度。把候选数量完整枚举出来是否可行不行才考虑二分答案。二分答案的价值不在于“高级”而在于用 log 倍的计数代价换掉构造全集的代价。计数代价不低时这个交换就不划算。我见过不少同学做这题时明明 n 只有 500完全可以直接 O(n² log n)却非要套二分答案代码长一倍还因为浮点精度问题反复 WA。学会判断“该不该用”比学会一个套路更重要这也是从普及走向提高组的台阶。5.3 我踩过的一个坑二分边界开太小导致答案被截断最后分享一个实际调试经历。第一次写这题时我图省事把 hi 直接设成 1e9因为我想着分数最小也是 1 除以最大值最大不会超过最大值除以 1给个 1e9 应该足够。结果题目数据范围里 a[i] 可以到 2e9正确答案直接超出我的上界二分死活找不到正确值整段代码在小数据上又是对的排查了半小时才发现是上界写死的问题。后来我改成排序后 hi a.back() / a[0]一切正常。这个教训告诉我二分答案的上下界必须由数据结构动态给出而不是拍一个看似够大的常数。上界过小截断答案下界过大漏掉最小值都是隐蔽又致命的问题。第二个坑是 k 的类型。当时我想 n 最大 10⁵k 最多也就 n² 也就是 10¹⁰但代码里 k 用了 int读入大 k 直接溢出成负数导致 countLess(mid) k 永远成立二分一路把 hi 压低到 lo答案完全不对。把所有涉及数量计数和 k 的变量全部改成 long long 之后问题立刻消失。现在再看到“二分查找”标签的题我的第一反应已经从“排个序”变成“要不猜一下答案”这个后遗症就是这道题留给我最宝贵的东西。