当前位置：首页 > news >正文

【Java】零基础蓝桥杯算法学习——二分查找

news 来源：原创 2024/5/21 16:24:09

算法模板一:

// 数组arr的区间[0,left-1]满足arr[i]<k,[left,n-1]满足arr[i]>=k;Scanner scan = new Scanner(System.in);int[] arr = {1,2,3,4,5};int left = 0,right = arr.length-1;int k = scan.nextInt();while(left<right) {//left==right时退出循环int mid = (left+right)/2;//当区间长度为偶数时，mid取区间靠左端点if(arr[mid]>=k) right = mid;else left = mid+1;}

算法模板二：

// 数组arr的区间[0,left]满足arr[i]<=k,[left+1,n-1]满足arr[i]>k;Scanner scan = new Scanner(System.in);int[] arr = {1,2,3,4,5,6};int left = 0,right = arr.length-1;int k = scan.nextInt();while(left<right) {//left==right时退出循环int mid = (left+right+1)/2;//当区间长度为偶数时，mid取区间靠右端点if(arr[mid]>k) right = mid-1;else left = mid;}

例题一：蓝桥杯2018真题：递增三元组

输入示例:

1 1 1

2 2 2

3 3 3

输出示例：27

代码示例：

import java.util.Arrays;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n = scan.nextInt();int[] a = new int[n];int[] b = new int[n];int[] c = new int[n];for(int i=0;i<n;i++) a[i] = scan.nextInt();for(int i=0;i<n;i++) b[i] = scan.nextInt();for(int i=0;i<n;i++) c[i] = scan.nextInt();Arrays.sort(a);Arrays.sort(b);Arrays.sort(c);int[] B = new int[n];for(int i=0;i<n;i++) {int l=0,r=n-1;while(l<r) {int mid = (l+r)/2;if(c[mid]>b[i]) r=mid;else l=mid+1;}if(c[l]>b[i]) B[i]=n-l;}long[] sum = new long[n+1];for(int i=1;i<=n;i++) sum[i]=sum[i-1]+B[i-1];long ans=0;for(int i=0;i<n;i++) {int l=0,r=n-1;while(l<r) {int mid = (l+r)/2;if(b[mid]>a[i]) r=mid;else l=mid+1;}if(b[l]>a[i]) ans+=(sum[n]-sum[l]);}System.out.println(ans);scan.close();}
}

例题二：蓝桥杯2017真题：分巧克力

输出：2

代码示例：

import java.util.Scanner;
public class Main {public static void main(String[] args)  {Scanner scan = new Scanner(System.in);int n = scan.nextInt();int k = scan.nextInt();int[] h = new int[n];int[] w = new int[n];for(int i=0;i<n;i++) {h[i]=scan.nextInt();w[i]=scan.nextInt();}int l=0,r=(int)1e5;while(l<r) {int mid=(l+r+1)/2;if(check(mid,h,w,k))  l=mid;else r=mid-1;}System.out.println(l);scan.close();}public static boolean check(int mid,int[] h,int[] w,int k) {int ans=0;for(int i=0;i<h.length;i++) {int res = (h[i]/mid)*(w[i]/mid);ans+=res;}return ans>=k;}
}