算法1
思路:这个题用二分真的很巧妙 res+=(h[i]/mid)*(w[i]/mid),这一步是整个题的关键
C++ 代码
#include<iostream>
#include<cstdio>
using namespace std;
const int N=100010;
int n,k;
int h[N],w[N];//h表示蛋糕的高度,w表示长度
bool check(int mid){
int res=0;//res表示一共可以分多少块
for(int i=0;i<n;i++){
res+=(h[i]/mid)*(w[i]/mid);//关键!!!
if(res>=k) return true;//满足返回true
}
return false;
}
int main(){
scanf("%d%d",&n,&k);//处理输入
for(int i=0;i<n;i++)scanf("%d%d",&h[i],&w[i]);
int l=1,r=1e5;
while(l<r){
int mid=(l+r+1)/2;
if(check(mid))l=mid;//这里mid=l是因为蛋糕分的过程中大于某一临界值就不能再分了,就比如6*5
//蛋糕分成边长为3的时候就是临界值,大于的3的时候就不能再分了,因此满足料件的二分是在二分的右半部分
else r=mid-1;
}
printf("%d\n",r);//最后写r或者l都可以
return 0;
}