AcWing 1227. 分巧克力
原题链接
简单
作者:
星野爱
,
2024-04-05 10:47:11
,
所有人可见
,
阅读 2
$\large{\color{Magenta}二\color{Magenta}分\color{Magenta}答\color{Magenta}案}$
#include <bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
const int M = 1e5+10;
int N, K, H[M], W[M], l=1, r;
void Init(){
cin >> N >> K;
for(int i=1;i<=N;i++){
cin >> H[i] >> W[i];
r = max(r, min(H[i],W[i]));
}
}
bool Check(int mid){
int cnt = 0;
for(int i=1;i<=N;i++){
int a = H[i], b = W[i];
cnt += (a/mid)*(b/mid);
if(cnt>=K) return true;
}
return false;
}
int Binary_ans(){
while(l<r){
int mid = (l+r>>1)+1;
if(Check(mid)) l = mid;
else r = mid - 1;
}
return l;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
Init();
cout << Binary_ans() << endl;
return 0;
}