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

例3 题目链接：hihoCoder1692

image

 给定N个不同质数，P1, P2, … PN。每个质数Pi作为分母都能产生Pi-1个真分数：1/Pi, 2/Pi, 3/Pi, … Pi-1/Pi。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小的分数。这个算法时间复杂度的瓶颈在对所有分数排序上。考虑到分数一共有ΣPi-N个，所以这个算法的时间复杂度是O((ΣPi-N)log(ΣPi-N))。根据题目给出的数据范围，大约能通过70%的数据

思路2

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

image

 多路归并的伪代码如下：

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  对于一个Pi可以求，“有几个分数小于等于x”，那么对于所有的Pi都可以循环求出来，所以我们可以求“在所有分数中，小于等于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

image

 如上图所示，黄色的小方块代表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)来二分，这样到底要二分多少次？  考虑到题目的范围，二分的次数大概是log(P^2)=2log(P)次，其中P是Pi的最大值。因为P1和P2是其中最大的两个质数，那么任意两个分数的差不会小于1/(P1×P2)。所以在我们二分的过程中，误差（也就是r-l差）在缩小到1/(P1×P2)之前就一定找到满足条件的m了。而查找范围从1缩小到1/(P1×P2)，每次缩小一半，总共缩小的次数不多于log(P1×P2)+1次  说回程序，考虑到之前伪代码中Cnt函数和Max-Leq函数有类似的循环代码。所以在上面的代码中我们把Cnt函数的逻辑和Max-Leq的逻辑写在一起了。在i循环中一边算出来“小于等于m的分数有多少个“，保存在cnt变量里；同时也算出来“小于等于m的最大分数“，是bestz/bestm  这时如果cnt等于K，就直接输出bestz/bestm。否则把范围缩小一半，继续尝试。 整个算法的时间复杂度是O(Nlog(P))的，可以通过所有的数据