//分巧克力,一块ab大小的巧克力,想分成nn大小的小块,试问可以分为几块?
//&&&&(1)(a/n)*(b/n):长可以分得的最大整数与宽可以分得的最大整数之积,而不是简单的面积相除
//&&&&(2)枚举最大长度的时候超时,可以适当缩小一个数量级(投机取巧的办法)
#include <iostream>
using namespace std;
const int N=1e5+10;
int n,k;
int row[N],col[N];
int main()
{
scanf("%d%d",&n,&k);
for(int i=0;i<n;i++)
cin>>row[i]>>col[i];
int res=10000;//从最大长度100000开始枚举,只能过部分数据集,其他会超时
//可以碰运气,缩小一点数据范围
while(res--){
//暴力求解,不断枚举可以分得的巧克力长度,从大到小枚举,则第一个满足条件的就是最大的
int sum=0;//不同的长度下需要置为0
for(int i=0;i<n;i++)//对每块巧克力求可以分得的块数
{
int sum1,sum2;
sum1=row[i]/res;
sum2=col[i]/res;
sum+=sum1*sum2;
} //&&&&&&&&&&&数学问题,正方形巧克力可以分得的块数就是长的最大数量*宽的最大数量(而不是总面积相除)
if(sum>=k) break;
}
cout<<res<<endl;
return 0;
}
----------
#include <iostream>
using namespace std;
const int N=1e5+10;
int n,k;
int row[N],col[N];
bool check(int mid){
int sum=0;//不同的长度下需要置为0,mid的值就是一个长度
for(int i=0;i<n;i++)//对每块巧克力求可以分得的块数
{
int sum1,sum2;
sum1=row[i]/mid;
sum2=col[i]/mid;
sum+=sum1*sum2;
} //&&&&&&&&&&&数学问题,正方形巧克力可以分得的块数就是长的最大数量*宽的最大数量(而不是总面积相除)
if(sum>=k) return true;
else return false;
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=0;i<n;i++)
cin>>row[i]>>col[i];
int l=1;
int r=100000;
int max=0;
while(l<=r){
int mid=(l+r)>>1;
if(check(mid))
{ max=mid;//找到一个先假定其为max,到后面继续找大的,找不到就输出
l=mid+1; //mid满足,但我们需要找最大的,所以还需要mid+1去判断
}
else r=mid-1;
}
cout<<max<<endl;
return 0;
}