2021/1/20 二分法实现分巧克力
xhhh其实是刚好刷完剪绳子的题,看到y总的二分思路就拿来用上了。
逆向思维确实很棒啊,大家都多用二分呀
代码很简单,就不用题解讲解了(少数几个题不用看视频做的哈哈哈)
题目描述
参考文献
时间复杂度O(nlogn)
C++ 代码
#include <iostream>
using namespace std;
const int N =100010;
int cho[N][2];
int main(){
int n,k;
cin >> n>> k;
for(int i = 0; i<n ; i++)
cin>> cho[i][0]>>cho[i][1];
int l = 1, r = 100000;
while(l<r){
int mid = (l+r+1)/2;
int res = 0;
for(int i = 0; i< n;i++){
res +=(cho[i][0]/mid)*(cho[i][1]/mid);
}
if(res >=k)
l = mid;
else
r = mid-1;
}
cout << l<<endl;
return 0;
}