蓝桥杯刷题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 = 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<n;i++){h[i] = scan.nextInt();w[i] = scan.nextInt();}int L = 1;int R = max;while(L> 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= 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++; // 可以搬走elsepos = stone[i]; // 不能搬走if (num <= m) return true; elsereturn 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<n;i++) { // * 0,1,1,2,2,infarr[i] = scan.nextLong()+arr[i-1];}arr[n] = arr[n-1]+1<<10;//对岸设置为无穷大int l=0;int r = n;while(l<r) {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<n-k;i++) {//任意k个大小的区间大于等于2*xif(arr[i+k]-arr[i] <2*x)return false;}return true;}}