MENU

二分查找与二分答案(4)

June 15, 2018 • Read: 5194 • 算法阅读设置

例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)$的,可以通过所有的数据

Last Modified: November 9, 2021
Archives Tip
QR Code for this page
Tipping QR Code
Leave a Comment

2 Comments
  1. xiaomo xiaomo

    萌新看不懂,难受

    1. mathor mathor

      @xiaomo没事没事,不懂可以问我