题目描述 儿童节那天有 K 位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。 小明一共有 N 块巧克力，其中第 i 块是 H_i\times W_i 的方格组成的长方形。为了公平起见， 小明需要从这 N 块巧克力中切出 K 块巧克力分给小朋友们。切出的巧克力需要满足：

• 形状是正方形，边长是整数；
• 大小相同；

例如一块 6\times 5 的巧克力可以切出 6 块 2\times 2 的巧克力或者 2 块 3\times 3 的巧克力。 当然小朋友们都希望得到的巧克力尽可能大，你能帮小明计算出最大的边长是多少么？

输入描述 第一行包含两个整数 N、K（1\le N,K\le 10^5）。 以下 N 行每行包含两个整数 H_i,W_i（1\le H_i,W_i\le 10^5）。 输入保证每位小朋友至少能获得一块 1\times 1 的巧克力。

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

输入输出样例 输入 2 10 6 5 5 6 输出 2

这道题使用了贪心算法和二分算法

所谓贪心，在此处的算法应用就是如果说一个尺寸为S的正方形巧克力能够提供给全部小朋友，那么这个尺寸能不能再大一点，也就是能不能为S＋１或者S＋２，直到S＋ｎ已经不能满足全部小朋友为止，所谓二分，在这里就是不遍历全部尺寸，而是选择一个区间，这个区间取一个中间值，如果这个中间值不能满足全部小朋友，我们可以把max换成中间值-1（已知中间值不可用，那么取小一个），然后再在min和新max中再取一个中间值，如此反复直到某个值可以满足小朋友。

下面是解题思路

我们接受了巧克力的数量N，小朋友的数量K，每块巧克力的长H和宽W

用两个数组存储长和宽，写一个函数，这个函数输入给定的一个正方形的尺寸，输出这些巧克力是否能被切成K块（是则1，否则0），然后把这个函数应用到贪心和二分上面

有如下过程:

确定二分区间–> 确定初始尺寸mid(二分点)–>函数检查

函数检查输出1–>不妨把尺寸变大（二分点增加）,最小值为二分点＋1–>函数检查

函数检查输出0–>不妨把尺寸缩小(二分点减少),最大值为二分点-1–>函数检查

直到min > max就结束（二分结束点）

代码实现：

<code>#include <stdio.h>
long long int h[100000],w[100000];
int check(long long int x,long long int n,long long int k)//x代表正方形的边长 
{
	long long int i , total = 0;//total能切出的整数 
	for(i=0;i<n;i++)
	{
		total += (long long int)((h[i]/x) * (w[i]/x));
/*上面检查了巧克力能被分成尺寸为x的正方形的数量，h[i]/x代表着长能放置多少个正方形,
w[i]/x代表着宽能放置多少个正方形，两者一乘就是这个长方形放置正方形的总数*/
		if (total >=k) return 1;
	}
	if(total >=k) return 1;
	else return 0;
}

int main(void)
{
	int check(long long int x,long long int n,long long int k);
	long long int n,k,x;
	scanf("%lld %lld",&n,&k);
	for(x=0;x<n;x++)
	{
		scanf("%lld %lld",&h[x],&w[x]);
	}
	
	//二分算法加贪心 
	long long int left=1,right=100000,ans,mid;
	while(left<=right) //左区域一定小于或等于右区域
	{
		mid = (right+left)/2;//中间变量 
		if(check(mid,n,k) == 1)
		{
			ans = mid;
			left = mid+1;
		}
		else  right = mid-1;
	} 
	printf("%lld",ans);
	return 0;
}</code>