標(biāo)題： 分巧克力
兒童節(jié)那天有K位小朋友到小明家做客凤巨。小明拿出了珍藏的巧克力招待小朋友們。
小明一共有N塊巧克力洛搀，其中第i塊是Hi x Wi的方格組成的長(zhǎng)方形敢茁。
為了公平起見(jiàn)，小明需要從這 N 塊巧克力中切出K塊巧克力分給小朋友們留美。切出的巧克力需要滿(mǎn)足：
1. 形狀是正方形彰檬，邊長(zhǎng)是整數(shù)
2. 大小相同
例如一塊6x5的巧克力可以切出6塊2x2的巧克力或者2塊3x3的巧克力。
1x6 2x6
當(dāng)然小朋友們都希望得到的巧克力盡可能大谎砾，你能幫小Hi計(jì)算出最大的邊長(zhǎng)是多少么逢倍？
輸入
第一行包含兩個(gè)整數(shù)N和K。(1 <= N, K <= 100000)
以下N行每行包含兩個(gè)整數(shù)Hi和Wi景图。(1 <= Hi, Wi <= 100000)
輸入保證每位小朋友至少能獲得一塊1x1的巧克力较雕。
輸出
輸出切出的正方形巧克力最大可能的邊長(zhǎng)。
樣例輸入：
2 10
6 5
5 6
樣例輸出：
2
資源約定：
峰值內(nèi)存消耗（含虛擬機(jī)） < 256M
CPU消耗 < 1000ms
請(qǐng)嚴(yán)格按要求輸出挚币，不要畫(huà)蛇添足地打印類(lèi)似：“請(qǐng)您輸入...” 的多余內(nèi)容亮蒋。
所有代碼放在同一個(gè)源文件中，調(diào)試通過(guò)后妆毕，拷貝提交該源碼慎玖。
不要使用package語(yǔ)句。不要使用jdk1.7及以上版本的特性笛粘。
主類(lèi)的名字必須是：Main趁怔，否則按無(wú)效代碼處理。
我們的目的是分出最大的巧克力塊薪前，并且滿(mǎn)足小朋友润努。
思路：巧克力塊最寬為10000，我們從10000寬度切起序六，不能就5000任连，就能從大到小選擇到最合適的寬度和塊數(shù)了蚤吹，在得到塊數(shù)剛剛大于小孩數(shù)的時(shí)候就可以調(diào)整得到答案了例诀。
藍(lán)橋杯如果十題里面都沒(méi)發(fā)現(xiàn)用到二分查找随抠，那么你應(yīng)該開(kāi)始注意了！一般會(huì)考一題繁涂。
package com.company;
import java.util.Scanner;
public class Main {
static int[] H = new int[100001];
static int[] W = new int[100001];
static int childs;
static int chos;
public static void main(String[] args) {
// write your code here
Scanner scanner = new Scanner(System.in);
chos = scanner.nextInt();
childs = scanner.nextInt();
for (int i = 0;i<chos;i++)
{
H[i] = scanner.nextInt();
W[i] = scanner.nextInt();
}
//我們要分出最大的巧克力,并且滿(mǎn)足小朋友
//我們以寬為10000的巧克力為最大拱她，以寬為1的巧克力最小
int low = 1;
int high = 10000;
int mid = (low+high)/2;
while (low<high-1){
mid = (low+high)/2;
if (cutChoByWidth(mid))
{//分出來(lái)的巧克力太多了，需要再切大塊點(diǎn)(寬點(diǎn) 增加mid)
low = mid;
}else
{
high = mid;
};
}
System.out.println(low);
}
private static Boolean cutChoByWidth(int width){
//按寬切出來(lái)的塊數(shù)
int parts = 0;
int h , w ;
for (int i = 0; i < chos; i++) {
//求出可以完成該寬度的個(gè)數(shù)
h = H[i]/width;
w = W[i]/width;
parts += h*w;
}
if (parts<childs){
//分出來(lái)的塊不夠小孩吃
return false;
}else {
return true;
}
}
}
