深入理解二分查找（二、二分答案）

二分答案

    如果已知候选答案的范围[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;
}