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

例3 题目链接:hihoCoder1692

 给定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小的分数。这也是一个很经典的问题,可以用多路归并

 多路归并的伪代码如下:

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

 如上图所示,黄色的小方块代表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))的,可以通过所有的数据

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏bboysoul

1079: 输出入门

描述:计算A+B 输入:输入数据有多组。每组一行,为两个整数A, B。输入以0 0结束。 输出:输出A+B的值,每组数据之间保留一个空行。 样例输入:1 ...

643
来自专栏TensorFlow从0到N

讨厌算法的程序员 7 - 归并排序的时间复杂度分析

? 递归树 上一篇归并排序基于分治思想通过递归的调用自身完成了排序,本篇是关于归并排序的最后一部分——分析其时间复杂度。 这个过程中会解释清楚在各种时间复杂度...

2346
来自专栏程序生活

Leetcode-Easy 887. Projection Area of 3D Shapes

当时自己没有想到好办法,就是按部就班的分别求三个面的面积,注意求xy的面积的时候需要考虑grid[i][j]值是否为0

722
来自专栏King_3的技术专栏

leetcode-59-螺旋矩阵 II

给定一个正整数 n,生成一个包含 1 到 n^2 所有元素,且元素按顺时针顺序螺旋排列的正方形矩阵。

763
来自专栏数据结构与算法

洛谷T21776 子序列

题目描述 你有一个长度为 nn 的数列 ,这个数列由 0,10,1 组成,进行 mm 个的操作: 1~l~r1 l r :把数列区间 [l, r][l,r] ...

2978
来自专栏人工智能LeadAI

讨厌算法的程序员 | 第七章 归并排序的时间复杂度分析

上一篇归并排序基于分治思想通过递归的调用自身完成了排序,本篇是关于归并排序的最后一部分——分析其时间复杂度。 这个过程中会解释清楚在各种时间复杂度中经常看到的一...

34711
来自专栏Coding迪斯尼

如何进入Google,面试算法之道:在双升序二维数组中的快速查找

1013
来自专栏数据结构与算法

1729 单词查找树 2000年NOI全国竞赛

1729 单词查找树 2000年NOI全国竞赛 时间限制: 2 s 空间限制: 128000 KB 题目等级 : 大师 Master 题目描述 D...

3385
来自专栏小樱的经验随笔

HDU 2080 夹角有多大II

夹角有多大II Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (J...

26210
来自专栏和蔼的张星的图像处理专栏

28. 搜索二维矩阵二分法

写出一个高效的算法来搜索 m × n矩阵中的值。 这个矩阵具有以下特性: 每行中的整数从左到右是排序的。 每行的第一个数大于上一行的最后一个整数。 样例...

552

扫码关注云+社区