思路:这道题需要采用二分思想。这道题需要满足两个条件:1至少分成k个正方形巧克力 2所分成的巧克力的变成要尽量大
一个a*b的矩形能够分成边长为i的正方形的个数=(a/i)*(b/i),这个公式自己模拟下可知
- 我们采用枚举最大边长来搜索,枚举时采用二分思想,left=1,right=所输入的最大边
- 外层循环枚举最大边长,内层一个for循环扫过所输入的巧克力边长,循环结束后得到能够把所有的巧克力分成边长为mid的正方形的个数cnt
- 比较cnt和k的值,如果cnt<k,则left = mid +1,继续枚举
- 如果cnt>=k,r = mid - 1,在这里面取最大的那个mid作为答案
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5+6;
int H[N];
int W[N];
int main()
{
int n,k;
cin>>n>>k;
int maxt = -1;
for(int i=1;i<=n;i++)
{
cin>>H[i]>>W[i];
int b = max(H[i],W[i]);
if(b>maxt) maxt = b;
}
int l = 1;
int r = maxt;
int ans = -1;
while(l<=r)
{
int mid = l + (r-l)/2;
int cnt = 0;
for(int i=1;i<=n;i++)
{
cnt += (H[i]/mid)*(W[i]/mid);
}
if(cnt<k)
{
r = mid - 1;
}
else
{
l = mid + 1;
if(mid>ans) ans = mid;
}
}
cout<<ans<<endl;
return 0;
}