#include <iostream>
using namespace std;
const int MAX = 1e5+5;
struct node
{
int x,y;
};
node a[MAX];
int n;
int ok(int e)//现在的边长
{
int ans = 0;
for(int i=0;i<n;i++)
{
int x = a[i].x,y = a[i].y;
int k1,k2;
k1 = x/e,k2 = y/e;
ans += k1*k2;
}
return ans;
}
int main()
{
int k;
scanf("%d %d",&n,&k);
for(int i=0;i<n;i++)
scanf("%d %d",&a[i].x,&a[i].y);
int le = 1,ri = 2*1e5;
int mid;
int ans = 0;
while(le <= ri)
{
mid = (ri+le)/2;
int now = ok(mid);
if(k > now)
ri = mid-1;
else if(k <= now)
{
le = mid+1;
ans = max(ans,mid);
}
}
printf("%d",ans);
return 0;
}
大致想法:
和昨天一样的,我们肯定是要一个一个枚举每一个可能的边长,最容易想到的就是二分
然后我们根据当前枚举的边长,去试探此边长我们能获得几个巧克力,然后再与要求的巧克力个数进行比较
所以关键在于如何由当前枚举边长获取巧克力个数
通过观察发现:
1.S(巧克力面积) >= L²m (L是枚举的边长,m是个数)
2.若有m = ab,那么存在a,b使得 x >= La and y >= Lb(这里x,y分别是拥有的巧克力边长)
所以这道题关键在于求a,b的最值…
也很简单就是int(x/L)和int(y/L)
然后只要当前巧克力的个数大于等于K我们就记录下来
取最大的就完事咯