AcWing 1227. 分巧克力
原题链接
简单
#include<cstdio>
#include<map> //使用pair必须要加该头文件
//(要使用 pair,应先添加头文件 #include <utility>,并在头文件下面加上 using namespace std; ,然后就可以使用了)
//由于 map 的内部实现中涉及 pair,因此添加 map 头文件时会自动添加 utility 头文件,
//此时如果需要使用 pair,就不需要额外再去添加 utility 头文件了
using namespace std;
const int N=1e5+10;
int n,k;
//简写习惯
typedef pair<int,int> PII;
#define x first
#define y second
PII s[N];
//判断条件是,在该边长mid下是否可以满足一共划分出k块
bool check(int mid){
int num=0;
for(int i=0;i<n;i++){
num+=(s[i].x/mid)*(s[i].y/mid);
}
if(num>=k)
return true;
else
return false;
}
//二分边长:当边长越小时,则一定能够满足要求
int main(){
//输入
scanf("%d %d",&n,&k);
for(int i=0;i<n;i++)
scanf("%d%d",&s[i].x,&s[i].y);
//二分过程
int l=0,r=1e5;
while(l<r){
int mid=(l+r+1)/2; //mid代表边长
if(check(mid))
l=mid;
else
r=mid-1;
}
printf("%d",l);
return 0;
}