AcWing 1227. 分巧克力
原题链接
简单
作者:
acw_yxy
,
2021-01-15 18:45:16
,
所有人可见
,
阅读 352
算法1
(二分法) $O(logn)$
C++ 代码
// 整数二分
#include <iostream>
#include <vector>
using namespace std;
vector<pair<int, int>> v;
int N, K;
bool check(int x)
{
int res = 0;
for(int i = 0; i < v.size(); i ++)
res += (v[i].first / x) * (v[i].second / x);
if(res >= K) return true;
return false;
}
int main()
{
cin >> N >> K;
for(int i = 0; i < N; i ++)
{
int m, n;
cin >> m >> n;
v.push_back({m, n});
}
// 二分
int l = 1, r = 1e5;
while(l < r)
{
int mid = l + r + 1 >> 1;
if(check(mid)) l = mid;
else r = mid - 1;
}
cout << l;
return 0;
}