`

深入理解二分查找(二、二分答案)

 
阅读更多

二分答案

    如果已知候选答案的范围[min,max],有时候我们不必通过计算得到答案,只需在此范围内应用“二分”的过程,逐渐靠近答案(最后,得到答案)!


一、何时可以使用“二分答案”

    不是任何题目都适合使用“二分答案”的,我Sam观察到一般有以下的一些特征:


    A. 候选答案必须是离散的 ,且已知答案的范围是:[最小值min, 最大值max] (连续区间上不能进行二分操作)

 

        例如,在题目“Kth Largest 第k大的数”中 ==> 答案是闭区间[a[1]b[1], a[n]b[n]]上的正整数
        例如,在题目“Drying 烘干衣服”中 ==> 烘干时间t∈[0,maxT], maxT=max{a[i]}


    B. 候选答案在区间[min,max]上某种属性一类一类的排列这样就能在此属性上进行二分操作 ),各个类别不交错混杂

 

        例如,在题目“Kth Largest 第k大的数”中 ==>

                 (候选答案)第k大的数的值:              a[1]b[1],  ... , a[n]b[n]

                 (属性分类)>这个乘积的数有多少:      n^2-1     ...      0

 

        例如,在题目“Drying 烘干衣服”中 ==>

                 (候选答案)烘干时间:  t=0,  t=1,  t=2,  t=3,  ...,  t=maxT-1,  t=maxT

                 (属性分类)能否烘干:  不能  不能   不能   能     ...    能               能


    C. 容易判断某个点 是否为答案(即二分过程中,mid指向的点是否为答案)
        例如,在题目“Kth Largest 第k大的数”中 ==> λ∈[ a[1]b[1], a[n]b[n] ]

                 对于某个候选答案,如果“>λ的乘积个数"<k   && “>λ-1的乘积个数”≥k ,则答案为λ

 

        例如,在题目“Drying 烘干衣服”中 ==>

                 需要寻找第一个出现的“能”(true),即如果check(mid-1)==false && check(mid)==true ,则答案为mid.

----------------------------------------------------------------------------------------------------------------------------------

二、举例

 

例一、Kth Largest       第k大的数

题目来源: http://acm.hrbeu.edu.cn/index.php?act=problem&id=1211

TimeLimit: 1 Second   MemoryLimit: 32 Megabyte

Description

There are two sequences A and B with N (1<=N<=10000) elements each. All of the elements are positive integers. Given C=A*B, where '*' representing Cartesian product, c = a*b, where c belonging to C, a belonging to A and b belonging to B. Your job is to find the K'th largest element in C, where K begins with 1.

Input

Input file contains multiple test cases. The first line is the number of test cases. There are three lines in each test case. The first line of each case contains two integers N and K, then the second line represents elements in A and the following line represents elements in B. All integers are positive and no more than 10000. K may be more than 10000.

Output

For each case output the K'th largest number.

Sample Input

2
2 1
3 4
5 6
2 3
2 1
4 8

Sample Output

24
8


【题解】:直接二分答案,然后判断答案的正确性。
               假设当前二分的答案为 t,那么:
               对于ai <= t的衣服,显然让它们自然风干就可以了。
               对于ai > t的衣服,我们需要知道该衣服最少用多少次烘干机。
               设该衣服用了x1分钟风干,用了x2分钟烘干机。
               那么有 x1 + x2 = t 和 ai <= x1 + x2 * k,联立两式可得 x2 >= (ai - t) / (k - 1),即最少使用次数为[(ai - t) / (k - 1)] 的最小上界。
               最后,判断一下总使用次数是否少于 t 即可。

 

【题解二】双重二分。先对两个序列A,B从大到小排序,然后可以我们进行第一重二分:对要求取的答案二分,即求取的答案在[A[n]*B[n],A[1]*B[1]]之间,取s1=A[n]*B[n],e1=A[1]*B[1],mid=(s1+e1)/2,那么我们去计算在序列C中大于等于这个mid值的个数是多少,当然不是算出这个序列来,而是进行第二次二分。我们对于两个序列可以这样处理,枚举序列A,二分序列B,也就是说对于每个A[i],我们去二分序列B,来计算大于等于mid值的个数。那么我们可以得到结束条件,当大于等于mid值的个数大于等于k,且大于mid值的个数小于k,那么答案就是这个mid。那么时间复杂度就为n*log(n)*log(n^2)了。

 

代码:

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<iostream>
#include<queue>
#include<map>
#include<vector>
#include<algorithm>
using namespace std;

/*测试用例:
3

4 1
1 2 3 4
5 6 7 8

4 2
1 2 3 4
5 6 7 8

4 3
1 2 3 4
5 6 7 8
*/

#define maxn 10010

int cases;   //用例 #  

int a[maxn],b[maxn];  //a[], b[]
int n;    //a[]和b[]的长度
int k;    //对于每个测试用例,找到第 k大的答案 

int ans;  //答案 

int cmp(const void *a,const void *b){
    return *(int *)b - *(int *)a;
}

//对于a[i],统计a[i]*b[1], a[i]*b[2], ... , a[i]*b[n]中 >t的乘积的个数 
int find(int t,int ai){
    int num=0;
    
    int s=1;
    int e=n;
    int mid;
    
    while(s<=e)    {
        mid=(s+e)>>1;
        if(ai*b[mid]>t){   //此时, a[i]*b[1], a[i]*b[2], ... , a[i]*b[mid]都 >t 
            num=mid;
            s=mid+1;
        }
        else
            e=mid-1;
    }
    
    return num;
}

//统计>t的个数 
int count(int t){
    int i,res=0;
    for(i=1;i<=n;i++){//枚举A中的每一个数字
        res+=find(t , a[i]); //对于a[i],二分序列 b[1]~b[n],find >t 的乘积个数
    }
    return res;
}

/*
  已知答案取值范围,二分枚举答案: 
  答案取值范围是[ s=a[n]b[n],e=a[1]b[1] ],在这个范围内找到第k大的数 a[i]b[j] 
*/
void solve(int s,int e){
    int mid=(s+e)>>1,t1,t2;

    while(s<=e)    {
        mid=(s+e)>>1;
        t1=count(mid);//统计大于mid值的个数 [mid+1,∞) 
        t2=count(mid-1);//统计大于等于mid值的个数 [mid,∞) 
        if( t1<k && t2>=k ){//找到答案
            ans=mid;
            return; 
        } 
        else if(t2<k)
            e=mid-1;
        else
            s=mid+1;
    }
}

int main(){
    int i,j;

    scanf("%d",&cases);
    while(cases--)    {
        scanf("%d%d",&n,&k);
        for (i = 1; i <= n; i++) scanf("%d", &a[i]);
        for (i = 1; i <= n; i++) scanf("%d", &b[i]);
        qsort(&a[1], n, sizeof(a[0]), cmp);  //从大到小排列 a[] 
        qsort(&b[1], n, sizeof(b[0]), cmp);

        ans=0;
        solve(a[n] * b[n], a[1] * b[1]);
        printf("%d\n", ans);
    }
    
    system("pause");
    return 0;
}

 

例二、POJ 3104  Drying  烘干衣服

题目来源:  http://poj.org/problem?id=3104

 

代码:

#include<cmath>
#include<iostream>
using namespace std;

int n;    //衣服件数 
int water[100010];    //水分 
int k;                //烘干机一次烘掉的水分 

int t=-1;    //最终答案:所有衣服干完的最少时间
int maxT=-1;    //所有衣服干完最长用时 

//用时不超过mid (<=mid)能否烘干衣服, T=O(n)
bool check(int mid){ 
    /*
      若某件衣服 i水分water[i]<mid,可以自然风干;否则需要烘。
      假设这件衣服自然风干用时 t1, 烘烤用时 t2.
          (1) t1+t2 = mid
          (2) t1+k*t2 >= water[i]
      ∴ t2 >= (water[i]-mid)/(k-1) 
      只需要判断使用烘干机的时间和是否 <= mid 即可 
    */ 
    double radTime=0;  //使用烘干机的总时间 
    
    for(int i=0;i<n;i++){
        if(water[i]>mid){
            radTime += ceil( (double)(water[i]-mid)/(double)(k-1) );  //衣服 a[i]需要烘的次数 
        }   //???1. ceil()函数 
    } 
    if(radTime<=mid)
        return true;
    else
        return false;
}

//所有衣服干完最少时间:[0,maxT], 二分答案 , T=O(log(maxT))O(n)
void solve(){
     int l=0;
     int r=maxT;
     int mid=(l+r)>>1;  //mid是在“二分答案 ”过程中每次观察的答案 
     
     //???2. 在二分查找中总结这种变形的二分查找: false, false, false, ..., false, true, true, ..., true
     //      找第一个出现的 true 的位置 
     while(l<=r){
         //每次进入循环,总能保证最终答案 t∈[l,r] 
         
         if(check(mid)==true){
             if(check(mid-1)==false){//再少用1个单位的时间都不能烘干 
                 t=mid;            //最终答案:最少用时mid 
                 return;
             }
             r=mid-1;
         }else{
             l=mid+1;
         }
         mid=(l+r)>>1;
     }
}

int main(void){
    scanf("%d",&n); //???3. 看scanf() 
    
    //while(n>0){
        //输入 
        int res=0;
        for(int i=0;i<n;i++){
            scanf("%d", &water[i]);
            maxT=maxT>water[i]?maxT:water[i];
        }
        scanf("%d",&k);
        
        //计算  & 输出 
        solve();
        printf("%d\n",t);
         
        //scanf("%d",&n);
    //}
    system("pause");
    return 0;
}
 

 

 

 

 

分享到:
评论

相关推荐

    深入理解二分查找(一、二分查找及其变体)

    在深入理解二分查找之前,我们需要先明确几个基本概念: 1. **有序数组**:二分查找的前提是数据已经按照升序或降序排列。对于无序数组,二分查找无法直接应用。 2. **中间元素**:每次查找都会选取数组的中间位置...

    二分查找解题

    本篇文章将深入探讨二分查找算法的递归实现,并结合大量的注释帮助理解。 首先,我们要明白二分查找的基本步骤: 1. 找到数组的中间元素。 2. 如果中间元素就是目标值,查找结束。 3. 如果目标值小于中间元素,...

    二分查找办法

    同时,了解这两种实现方式有助于我们更好地理解和改进二分查找算法,对于提升编程技能和解决复杂问题非常有帮助。 在Lecture7_BinarySearch1这个文件中,可能包含了关于这两种二分查找方法的详细讲解、示例代码和...

    C++ 二分查找法

    本文将深入探讨C++中实现二分查找法的具体细节、原理以及其在实际编程中的应用。 #### 一、二分查找法的基本原理 二分查找法的基本思想是通过不断将查找区间分为两半,从而快速定位目标值。具体步骤如下: 1. **...

    二分查找 & 二分答案 万字详解,超多例题,带你学透二分

    首先,我们来理解二分查找的基本步骤: 1. 计算数组的中间索引。 2. 检查中间元素是否是目标值。如果是,查找结束。 3. 如果目标值小于中间元素,那么在左半部分(即中间索引左侧)继续查找。 4. 如果目标值大于中间...

    Java二分查找示例代码

    下面我们将深入探讨Java实现二分查找的具体步骤、示例代码以及其应用场景。 一、二分查找原理 二分查找的基本思想是将数组分为两半,然后比较中间元素与目标值的关系。如果中间元素等于目标值,则查找成功;如果...

    MATLAB 二分查找法程序实现 .rar

    二分查找法是一种在有序数组中查找特定元素的高效算法,其基本...这样的编程练习有助于深入理解二分查找法,并提升在MATLAB环境下的编程能力。通过不断地实践和优化,你将能够更加熟练地运用二分查找法解决实际问题。

    C 二分查找算法.rar

    通过阅读和调试代码,你可以深入理解二分查找和顺序查找的工作原理,以及如何在实际项目中应用类模板。 总之,二分查找和顺序查找是两种重要的查找算法,各有其适用场景。了解并掌握这些算法对于提升编程技能和解决...

    erfenchaz.rar_二分查找_二分查找函数

    通过"erfenchaz.doc"文件,我们可以深入学习如何实现和测试二分查找,这对于提升我们的编程技能和理解数据结构的高效操作至关重要。记得实践是检验真理的唯一标准,动手编写并测试二分查找代码,将会使你对这个概念...

    C+++版二分查找

    本篇文章通过对给定代码的详细分析,不仅介绍了二分查找算法的基本概念,还深入解析了其具体的实现细节,包括冒泡排序和递归方法的应用。这些知识对于理解和掌握二分查找算法及其在实际编程中的运用具有重要的意义。

    查找算法:二分查找、顺序查找

    这里我们将深入探讨两种常见的查找算法:二分查找和顺序查找。 **一、顺序查找** 顺序查找是最基础的查找算法之一。它的工作原理是从数据集(如数组或列表)的第一个元素开始,逐个比较目标值与当前元素,直到找到...

    C语言程序设计实现二分查找算法

    在本课程设计报告中,我们将深入探讨如何使用C语言实现二分查找算法。二分查找是一种高效的搜索算法,尤其适用于已排序的数组或列表。它通过不断将搜索区间减半来快速定位目标值,大大提高了查找效率。以下是关于二...

    数据结构 二分查找程序代码

    本文将深入探讨二分查找(Binary Search)这一高效查找技术及其C语言实现。 #### 二分查找原理 二分查找是一种在有序数组中查找特定元素的搜索算法。它的工作原理是将目标值与数组中间元素进行比较:如果目标值等于...

    二分查找算法,很基本但很有用

    为了深入理解二分查找,你可以查阅HALFSCH.C的源代码,了解具体实现细节,也可以通过www.pudn.com.txt找到更多的学习资源和讨论。 总的来说,二分查找算法是一种基础且实用的搜索策略,尤其在大数据处理和高性能...

    (二分查找)二元搜索.zip

    通过学习和理解FORTRAN实现的二分查找程序,开发者可以深入掌握分治策略和数值计算语言的使用,这对于科学计算和工程应用领域的工作具有很高的价值。同时,这也是理解和优化其他编程语言中二分查找算法的基础。

    快速排序对数组排序,二分查找。

    快速排序和二分查找是计算机科学中非常基础且重要的算法,它们在数据处理和效率提升方面发挥着关键作用。快速排序是一种高效的排序算法,而二分查找则是一种在有序序列中寻找特定元素的有效方法。 快速排序由英国...

    二分查找的C实现

    下面我们将深入探讨二分查找的原理、C语言实现及其优化。 **二分查找的原理:** 1. 首先,我们需要一个已排序的数组。这是二分查找的前提条件,因为只有在有序的情况下,才能通过比较中间元素快速缩小查找范围。 2....

    计算机算法分析 二分查找 分治算法

    **二分查找与分治算法详解** 二分查找是一种基于分治策略的高效搜索算法,主要应用于有序数据集合。在给定的升序排列的数组a[0:n-1]中,二分查找的目标是找到特定元素x的位置,或者确认元素不在数组中。算法的基本...

    二分探索法查找数据课程设计

    二分探索法,又称二分查找法或二分搜索法,是一种高效的查找算法,尤其适用于已排序的数据集合。它的核心思想源于分治策略,通过不断缩小查找范围来快速定位目标值。在每次查找中,算法将查找区间分为两半,然后比较...

    二分查找和hash表的实现

    二分查找和哈希表是两种在计算机科学中广泛使用的数据结构和算法,它们在解决查找和检索问题时有着高效的表现。这篇文档将深入探讨这两种技术的原理、实现及应用场景。 首先,我们来讨论二分查找。二分查找,也称为...

Global site tag (gtag.js) - Google Analytics