二分查找与二分答案(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 条评论
登录 后参与评论

相关文章

来自专栏Java 源码分析

平衡搜索树

2-3树 ​ 其实仔细来看2-3树好像是 B 树的一个特例,它规定了一个节点要么有一个 key 要么有两个 key。 如果有一个 key 那么他就有两个子...

3039
来自专栏数据处理

TensorFlow入门1-minist

1633
来自专栏CreateAMind

keras doc 9 预处理等

用以生成一个batch的图像数据,支持实时数据提升。训练时该函数会无限生成数据,直到达到规定的epoch次数为止。

1922
来自专栏祥子的故事

python | pandas | 移动窗口函数rolling

6585
来自专栏desperate633

LintCode 寻找缺失的数题目分析方法二 交换法

给出一个包含 0 .. N 中 N 个数的序列,找出0 .. N 中没有出现在序列中的那个数。

763
来自专栏我是业余自学C/C++的

对角矩阵

1142
来自专栏人工智能LeadAI

机器学习实战 | 第二章:线性回归模型

线性回归(Linear Regression) 这个类是传统最小二乘回归的类.是最基础的线性回归的类. class sklearn.linear_model....

3147
来自专栏大数据挖掘DT机器学习

CART算法学习及代码实现

1.算法介绍 分类回归树算法:CART(Classification And Regression Tree)算法采用一种二分递归分割的技术,将当前的样...

4264
来自专栏机器学习算法原理与实践

用scikit-learn学习BIRCH聚类

    在BIRCH聚类算法原理中,我们对BIRCH聚类算法的原理做了总结,本文就对scikit-learn中BIRCH算法的使用做一个总结。

1213
来自专栏利炳根的专栏

学习笔记DL004:标量、向量、矩阵、张量,矩阵、向量相乘,单位矩阵、逆矩阵

线性代数,面向连续数学,非离散数学。《The Matrix Cookbook》,Petersen and Pedersen,2006。Shilov(1977)。

3590

扫码关注云+社区