二分法求解Java代码

儿童节那天有K位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。
小明一共有N块巧克力，其中第i块是Hi x Wi的方格组成的长方形。


为了公平起见，小明需要从这 N 块巧克力中切出K块巧克力分给小朋友们。切出的巧克力需要满足：


1. 形状是正方形，边长是整数
2. 大小相同


例如一块6x5的巧克力可以切出6块2x2的巧克力或者2块3x3的巧克力。


当然小朋友们都希望得到的巧克力尽可能大，你能帮小Hi计算出最大的边长是多少么？

输入：
第一行包含两个整数N和K。(1 <= N, K <= 100000)
以下N行每行包含两个整数Hi和Wi。(1 <= Hi, Wi <= 100000)
输入保证每位小朋友至少能获得一块1x1的巧克力。

输出：
输出切出的正方形巧克力最大可能的边长。

解题思路:

要求的是最大的边长，也就是从1开始到10000，找到其中最大的边长使得可以切出k个巧克力。

什么是最大的边？

就是当一个边a恰好可以切出大于或等于k个巧克力，而边长（a+1）却连k个巧克力都切不出来的时候，a就是最大的边。

怎么找？

利用二分可以很简单的做出来，当边长为mid切出的巧克力的数量大于等于k，且mid+1的边长切不出k个巧克力的时候，mid的值就是我们要求的值。

注意事项:
先看下面代码，注意while循环，我是r==l的时候也要循环，原因是：假如6×5的长方形，要3个蛋糕，假如我得到了2这个边，然后求得总巧克力数是6，大于k，然后l = mid+1，此时，l到r之间的所有数都不是我们要求的边，因为里面最小的数3只可以得到2个巧克力。但我们仍然会得到最终结果，原因是我们的sum一直小于k，r就会一直等于mid-1，当最后我们的边为3的时候，sum还是小于k，然后r还是等于mid-1，这个时候r就等于2了，这就是为什么r==l还要循环的原因。

那么为什么sum==k的时候还要继续遍历呢？

10 10
10 10 
10 10
10 10 
10 10 
10 10 
10 10 
10 10 
10 10 
10 10 
10 10

  看这个样例，当边为6的时候，sum的值为10，如果我们sum==k的时候就结束，肯定得不到我们需要的边。
  那为什么是当sum>=k的时候l=mid+1而不是当sum<=k的时候r=mid-1呢？
  因为我们求的是最大的边，以上面的例子，sum=10的时候，边可以是6，7，8，9，10
  我们求的是10，如果当sum<=k的时候r=mid-1，那无论当时我们的边是6，7，8，9，10中的哪一个，以后我们得到的边一定比那个边要小。

参考代码:

public class Main {
	public static void main(String[]args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int k = scanner.nextInt();
		int a[][] = new int[n][2];
		for (int i = 0; i < n; i++) {
			a[i][0]=scanner.nextInt();
			a[i][1]=scanner.nextInt();
		}
		int r = 100000;
		int l = 1;
		while (r>=l) {
			int mid = (r+l)/2;
			//切的巧克力的总数量
			int sum=0;
		//数学思维，长方形的长可以切多少个长度为x的正方形，宽可以切多少个长度为x的正方形，二者相乘就是真正可以切的正方形的数量
			for (int i = 0; i < a.length; i++) {
				sum = sum+(a[i][0]/mid)*(a[i][1]/mid);
			}
			//如果小于k，说明正方形太长了，巧克力不够
			if (sum=k) {
				l = mid+1;
			} 
		}
		System.out.print((r+l)/2);
	}

}