二分查找与二分答案（4）

例 3 题目链接：hihoCoder1692展开目录

给定 N 个不同质数，$P_1, P_2, …, P_N$。每个质数 $P_i$ 作为分母都能产生 $P_i-1$ 个真分数：$\frac {1}{p_i}, \frac {2}{p_i}, \frac {3}{p_i}, …, \frac {p_i-1}{p_i}$。N 个质数一起就能产生很多个真分数。因为这些作为分母的质数两两不同，所以这些真分数也都两两不同。最后问其中第 K 小的分数是多少？

我们看样例，一共有 2,3,5 三个质数。以 2、3、5 为分母，真分数有：1/2, 1/3, 2/3, 1/5, 2/5, 3/5, 4/5。把它们排一下序是：1/5, 1/3, 2/5, 1/2 , 3/5, 2/3, 4/5 。第 4 小的是 1/2 ，所以答案就是 1/2

思路 1展开目录

先把所有的分数存在一个数组里。然后对数组排序。最后直接输出第 K 小的分数。这个算法时间复杂度的瓶颈在对所有分数排序上。考虑到分数一共有 $\sum p_i - N$ 个，所以这个算法的时间复杂度是 $O ((\sum p_i - N) \times log (\sum p_i - N))$。根据题目给出的数据范围，大约能通过 70% 的数据

思路 2展开目录

把每一个分母 $p_i$ 都看成一个单独的数组。那么这个数组里的分数从小到大自然是 $\frac {1}{p_i}, \frac {2}{p_i}, \frac {3}{p_i}, …, \frac {p_i-1}{p_i}$。然后我们有 N 个这样的有序数组，我们想找到在所有数组中第 K 小的分数。这也是一个很经典的问题，可以用多路归并
多路归并的伪代码如下：

Q[] = {1,1,1,...}//Q[i]是P[i]对应得分子，初始值都是1
For i = 1...K
    求出Q[i]/P[i]中最小的分数Q[x]/P[x]
    If i == k
        print Q[x]/P[x]
    Else
        Q[x]++

上面伪代码的时间复杂度取决于 “求出 Q [i]/P [i] 中最小的分数 Q [x]/P [x]” 这一步如果用顺序查找，时间复杂度是 O (N)，肯定会超时

当然也可以用二分法，不过这个二分的思路不容易想到。首先假设我们有一个 [0,1] 之间的浮点数 x，比如 x=0.5，那么对于一个质数 Pi，我们很容易求出以 Pi 为分母的分数中，有几个分数小于等于 x。事实上答案就是 (int)(x * Pi)

举个例子，对于 x=0.5，Pi=5，x*Pi=2.5，下取整是 2，因为 1/5 和 1/5 两个分数小于 0.5，所以答案刚好是 2

对于一个 $p_i$ 可以求，有几个分数小于等于 x，那么对于所有的 $p_i$ 都可以循环求出来，所以我们可以求 “在所有分数中，小于等于 x 的数有多少个”，记作 cnt (x)，伪代码如下：

Cnt(x)
    Ans = 0
    For i = 1...N
        Ans += (int)(x * P[i])
return Ans

不难看出 cnt (x) 是一个递增函数。既然 cnt (x) 是递增函数，我们就可以用二分查找的算法，找到一个 x 满足 cnt(x) == K。这里的 K 就是题目里我们求第 K 小分数的 K。当然因为 x 的类型是浮点数，所以满足条件的 x 有无穷多个，实际上是一段实数区间。我们求出任意一个 x 就可以

对于样例，我们发现 x=0.55 就满足条件。因为对于分母等于 2，小于等于 x 的分数有一个 1/2; 对于分母等于 3，有一个 1/3；对于分母等于 5 有两个：1/5, 2/5。所以 cnt (x)=4 也等于 K

如上图所示，黄色的小方块代表 1/2，也就是分母是 2 的分数。2 绿色的小方块代表 1/3 和 2/3，也就是分母是 3 的分数。4 个蓝色的小方块代表 1/5, 2/5, 3/5, 4/5, 也就是分母是 5 的分数

现在我们找到了 cnt (0.55)=K。而我们要找第 K 小的分数，就可以转化成找小于等于 0.55 的分数中，最大的一个分数。要找到所有分数中，小于等于 0.55 的最大分数。可以先找分母是 2 的最大的是哪个，也就是所有黄色方块中在虚线之前的最大的分数 ，是 1/2；同理分母是 3 的绿色方块中，虚线之前最大的是 1/3；分母是 5 的蓝色方块中，虚线之前最大的是 2/5

最后我们再从 1/2, 1/3, 2/5 中找一个最大的，是 1/2，也就是答案。综上所述，要找到所有分数中，小于等于 x 的最大分数，复杂度是 O (N) 的，伪代码如下：

Max_Leq(x)
    Q = []
    For i = 1...N
        Q[i] = (int)(x * P[i])
return max(Q[i]/P[i])//返回Q[i]/P[i]中最大的

L = 0.0,R = 1.0
while(TRUE)
    m = (L + R) / 2
    If Cnt(m) = k
        print Max_Leq(m)
    If Cnt(m) < k
        L = m
    Else
        R = m

注意我们是在实数 [0, 1] 的范围二分 m，直到找到一个满足 cnt (m)=K 的 m，所以是 while (TRUE)。而且折半也是 L=m 和 R=m，不用 + 1 也不用 - 1 了。只要找到一个满足 cnt (m)=K 的 m，我们就去计算小于等于 m 的最大分数，也就是 Max_Leq (m)

#include <iostream>
using namespace std;
int n,k,p[1001];
int main()
{
    cin >> n >> k;
    for(int i = 0;i < n;i++)
        cin >> p[i];
    double l = 0.0,r = 1.0,m;
    while(true)
    {
        m = (l + r) / 2;
        long long cnt = 0,bestz = -1,bestm = -1;
        for(int i = 0;i < n;i++)
        {
            long long x = p[i] * m;
            cnt += x;
            if(bestz == -1)
            {
                bestz = x;
                bestm = p[i];
            }
            if((long long)bestz * p[i] < (long long)x * bestm)
            {
                bestz = x;
                bestm = p[i];
            }
        }
        if(cnt == k)
        {
            cout << bestz << '/' << bestm << endl;
            return 0;
        }
        if(cnt < k)
            l = m;
        else
            r = m;
    }
    return 0;
} 

大家可能会问，这个在实数 [0, 1] 的范围里，while (true) 来二分，这样到底要二分多少次？

考虑到题目的范围，二分的次数大概是 $logP^2=2logP$ 次，其中 $P$ 是 $P_i$ 的最大值。因为 $P_1$ 和 $P_2$ 是其中最大的两个质数，那么任意两个分数的差不会小于 $\frac {1}{P_1\times P_2}$。所以在我们二分的过程中，误差（也就是 r-l 差）在缩小到 $\frac {1}{P_1\times P_2}$ 之前就一定找到满足条件的 m 了。而查找范围从 1 缩小到 $\frac {1}{P_1\times P_2}$，每次缩小一半，总共缩小的次数不多于 $log (P_1\times P_2)+1$ 次

说回程序，考虑到之前伪代码中 cnt 函数和 Max-Leq 函数有类似的循环代码。所以在上面的代码中我们把 cnt 函数的逻辑和 Max-Leq 的逻辑写在一起了。在 i 循环中一边算出来 “小于等于 m 的分数有多少个 “，保存在 cnt 变量里；同时也算出来 “小于等于 m 的最大分数 “，是 $\frac {bestz}{bestm}$

这时如果 cnt 等于 K，就直接输出 $\frac {bestz}{bestm}$。否则把范围缩小一半，继续尝试。整个算法的时间复杂度是 $O (NlogP)$ 的，可以通过所有的数据