AcWing 1227. 分巧克力
原题链接
简单
作者:
Tanx_Y
,
2024-02-20 14:41:18
,
所有人可见
,
阅读 45
简易版
C++ 代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 5;
int n, k, m;
int h[N], w[N];
int main()
{
scanf("%d%d", &n, &k);
for(int i = 0; i < n; i++)
{
scanf("%d%d", &h[i], &w[i]);
int temp = min(h[i], w[i]);
m = max(temp, m);
}
int l = 1, r = m;
while(l < r)
{
int t = 0;
int mid = (l + r + 1) >> 1;
for(int i = 0; i < n; i++)
{
t += (h[i] / mid) * (w[i] / mid);
}
if(t >= k)
l = mid;
else
r = mid - 1;
}
cout<<l;
return 0;
}
二分?
是的,边长越小,对应的个数越多,是个单调序列,可以找恰好等于目标个数的边长
嗯