初始思路可以令最大正方形巧克力边长(max_bian)一点点缩小 直至数量满足 但是时间复杂度太高 因此选择简化外部循环
for(int j=1e5;j>=1;j--){
int max_bian=j;
int sum_k=0;
// 汇总切出来的巧克力总数
for(int i=0;i<n;i++){
// 每一个巧克力能切出几块边长为max_bian的正方形巧克力
sum_k+=(H[i]/max_bian)*(W[i]/max_bian);
}
// 数量满足K个小朋友 则max_bian为可以的边长
if(sum_k>=k){
printf("%d",max_bian);
break;
}
}
}
采用二分法简化外部循环
1.要注意是最大正方形巧克力边长(max_bian)的前驱而不是后继 max_bian的后继属于切大了数量不满足 前驱属于切小了但数量能够满足
2.check应该是边长(max_bian)切小了,块数超了 返回true,因此左指针右移 边长(max_bian)右移
#include<bits/stdc++.h>
using namespace std;
const int N=1e5;
vector<int> H(N,0);
vector<int> W(N,0);
int n,k;
bool check(int max_bian){
int sum_k=0;
// 汇总切出来的巧克力总数
for(int i=0;i<n;i++){
// 每一个巧克力能切出几块边长为max_bian的正方形巧克力
sum_k+=(H[i]/max_bian)*(W[i]/max_bian);
}
// 切小了 块数超了
if(sum_k>=k){
return true;
}else{
return false;
}
}
int main(){
cin>>n>>k;
// 记录每一个巧克力的宽高
for(int i=0;i<n;i++){
int h,w;
cin>>h>>w;
H[i]=h; W[i]=w;
}
int l=0;int r=1e5;
while(l<r){
int max_bian=(l+r+1)>>1;
// 这里应该是找前驱,足够数量(因此r要-1) 后继切大了,不够数量
if(check(max_bian)) l=max_bian;// 切小了,块数超了,左指针右移,max_bian右移 因此check应该是切小了返回true
else r=max_bian-1;// 切大了,右指针左移,max_bian左移
}
printf("%d",l);
}