侧边栏壁纸
博主头像
SeaDream乄造梦

Dream,Don't stop a day of hard and don't give up a little hope。 ——不停止一日努力&&不放弃一点希望。

  • 累计撰写 39 篇文章
  • 累计创建 20 个标签
  • 累计收到 13 条评论

目 录CONTENT

文章目录

java基础算法 二分法查找和基础原理,二分进阶灵活运用练习——小明分巧克力

SeaDream乄造梦
2022-02-21 / 0 评论 / 0 点赞 / 499 阅读 / 1,547 字
温馨提示:
亲爱的,如果觉得博主很有趣就留下你的足迹,并收藏下链接在走叭

二分法的时间复杂度是O (logn),是初学者都需要学的一项最基本算法,下面我们先展示原理在展示代码,然后在进阶练习

原理

在这里插入图片描述

代码:

public class A01_二分法 {
	public int search(int[] nums, int target) {
		int left = 0, right = nums.length - 1;
		int count = 0;
		while (left < right) {
			int mid = (left + right) / 2;
			if (nums[mid] >= target)
				right = mid;
			if (nums[mid] < target)
				left = mid + 1;
		} 
		while (left < nums.length && nums[left++] == target)
			count++;
		return count;
	}
	public static void main(String[] args) {
		A01_二分法 demo = new A01_二分法();
		int a[] = {1,3,4,4,6,7,8,10,13,14};
		System.out.println(demo.search(a,4));
	}
}

基础算法了解了,下面我们来进行一下升级叭!

分巧克力

题目

在这里插入图片描述

题解难点:

  1. 对于一个给定正方形边长x,给定长方形长l、宽w
  2. 正方形最多能分割成(l/x)*(w/x)块。
  3. 题意要求最小边界为1,最大为巧克力的最大边长
  4. 可以复制代码,把注释地方的输出解开,仔细研究一下原理
import java.util.Scanner;

public class 分巧克力 {
    public static void main(String[] args) {
        /**思路分析
         *   n块巧克力分给k位小朋友,设长方形长l,宽w。  分出的相等的正方形巧克力边长x
         *   一个长方形  最多可分l/x * w/x   (w>=x)个巧克力
         *   巧克力与
          */
        Scanner scanner = new Scanner(System.in);
        int n=scanner.nextInt(),k = scanner.nextInt();
        int [][] arr = new int[n][2];
        int max =0;//巧克力最大边长
        for (int i=0;i<n;i++) {
            for (int j=0;j<2;j++) {
                arr[i][j]=scanner.nextInt();
                if (arr[i][j]>=max) {
                    max = arr[i][j];
                }
            }
        }
        //		System.out.println(max);
    //    巧克力最大边长已求出,巧克力最小边长从1开始  用二分法开始累加,直到符合题意==》所有孩子均够分巧克力,且分到的最大
        int l=1,r=max;
        while (l<r){ //l<r,从小到大开始  逐个遍历直到l达到最大值,终止循环,输出l
            int mid = (l+r+1)/2;
            // System.out.println(mid);
            if (judge(arr,k,mid)){
                l=mid;
                // System.out.println("l: "+l);
            }else {
                r=mid-1;
                // System.out.println("r: "+r);
            }
        }
        System.out.println(l);

    }
//    写方法  传入数组,遍历数组,检测是否够孩子分
                                    //arr数组,n巧克力个数,k孩子人数,a每个孩子分到的巧克力边长
    public static boolean judge(int[][]arr,int k,int a) {
        int sum=0;
        for (int i=0;i<arr.length;i++) {
            sum  +=  arr[i][0]/a * arr[i][1]/a;
        }
        if (sum>=k) {
            return true;
        }
        return false;
    }
}
0

评论区