蓝桥杯刷题6--二分法

1. 二分法

注意二分法的应用条件是：序列是单调有序的，从小到大，或从大到小。在无序的序列上无法二分，如果是乱序的，应该先排序再二分。

1.1 代码实现

import java.util.*;
class Main {
    static int[] a = new int[105];
    static boolean check(int x, int mid) { return x <= a[mid]; }
    static int bin_search(int n, int x) {
        int L = 1;
        int R = n;
        while (L < R) {
            int mid = (L + R) / 2;
            if (check(x, mid))     R = mid;
            else                   L = mid + 1;            
        }
        return a[L];
    }
 
    public static void main(String[] args) {
        int n = 100;
        for (int i = 1; i <= n; i++)   a[i] = i;        
        int x = 68;
        System.out.println("x=" + bin_search(n, x));
    }
}

2. 习题

2.1 求阶乘

import java.util.*;
 
public class Main {
  public static long check(long mid){
      long count = 0;
      while(mid > 0){
        count += mid/5;
        mid /= 5;
      }
      return count;
    }
  public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        long k = scan.nextLong();
        long left = 0;
        long right = (long) Math.pow(10,19);
        while(left < right){
          long mid = (left + right)/2;
          if(check(mid) >= k) right = mid;
          else left = mid + 1;
        }
        if(check(right)==k) System.out.println(right);
        else System.out.println(-1);
        scan.close();
    }
}

2.2 分巧克力

import java.util.*;
public class Main {
    static int k,n;
    static final int max = 100010;
    static int h[] = new int[max];
    static int w[] = new int[max];
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        k = scan.nextInt();
        for(int i = 0;i
          h[i] = scan.nextInt();
          w[i] = scan.nextInt();
        }
        int L = 1;
        int R = max;
        while(L
          int mid = (L + R + 1) >> 1;
          if(check(mid)) L = mid;
          else R = mid-1;
        }
        System.out.println(L);
        scan.close();
    }
 
    public static boolean check(int d){
      int count = 0;
      for(int i = 0;i
        count += (h[i]/d) * (w[i]/d);
      }
      if(count >= k) return true;
      else return false;
    }
}

2.3 最小值最大化：跳石头

import java.util.Scanner;
public class Main {
    static int len, n, m;
    static int[] stone;
    static boolean check(int d) {
        int num = 0; // num记录搬走石头的数量
        int pos = 0; // 当前站立的石头
        for (int i = 1; i <= n; ++i)
            if (stone[i] - pos < d)         num++; // 可以搬走
            else                pos = stone[i]; // 不能搬走
        if (num <= m)       return true; 
        else            return false; 
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        len = scan.nextInt();
        n = scan.nextInt();
        m = scan.nextInt();
        stone = new int[n + 1];
        for (int i = 1; i <= n; i++){
          stone[i] = scan.nextInt();
        }
       int L = 0;
       int R = len;
        while (L < R) {
            int mid = L + (R - L) / 2;
            if (check(mid))  L = mid + 1; // 说明mid小了，调大一点
            else             R = mid - 1; // 说明mid大了，调小一点
        }
        if (!check(R))  R += 1;
        System.out.println(R);
        scan.close();
    }
}

2.4 青蛙过河

import java.util.*;
public class Main{
 
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n =scan.nextInt();
        int x = scan.nextInt();
        long[] arr = new long[n+1];//存放每一个石头的位置
        for(int i=1;i// * 0,1,1,2,2,inf
            arr[i] = scan.nextLong()+arr[i-1];
        }
        arr[n] = arr[n-1]+1<<10;//对岸设置为无穷大
        int l=0;
        int r = n;
        while(l
            int mid = (l+r)/2;
            if(check(mid,arr,n,x)) {
                r = mid;
            }else {
                l = mid+1;
            }
        }
        System.out.println(l);
        
    }
    public static boolean check(int k,long[] arr,int n,int x) {
        for(int i=0;i//任意k个大小的区间大于等于2*x
            if(arr[i+k]-arr[i] <2*x)
                return false;
        }
        return true;
    }
 
}