题目描述
分巧克力,二分法
样例
#include <iostream>
using namespace std;
int H[100100][2];
int n,k;
bool check(int lenth)
{
int cnt=0;
for(int i=0;i<n;i++)
{
cnt += ((H[i][0]/lenth) * (H[i][1]/lenth));
}
if(cnt>=k) return true;
return false;
}
int main()
{
cin>>n>>k;
for(int i=0;i<n;i++)
{
cin>>H[i][0]>>H[i][1];
}
int a=0,b=100000,mid=0;
for(int i=0;i<20;i++)
{
mid = (a+b)/2;
if(check(mid))
a=mid;
else
b = mid;
}
cout<<mid<<endl;
return 0;
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla