蓝桥杯真题——分巧克力（二分）

思路:

使用二分查找[1,1e5]，每次取中值作为正方形边长x，统计在所有巧克力中能分割出多少块边长为x的正方形
当正方形数量小于k时，我们知道边长越大能分割的数量越少，此时将区间更新为 [l,mid-1] 继续查找。
当正方形数量大于等于k时，猜测x可以更大且能满足>=k，将区间更新为[mid,r]

#include <iostream>
using namespace std;
const int N  = 1e5+10;
int n,k;

//存储每块巧克力的长宽
int qkl[N][3];

//统计所有巧克力能切割出多少块边长为x的正方形
int count(int x){
  int sum=0;
  for(int i=0;i<n;i++){
    sum+= (qkl[i][0]/x)*(qkl[i][1]/x);
  }
  return sum;
}

int main()
{
  cin>>n>>k;
  for(int i=0;i<n;i++)
    cin>>qkl[i][0]>>qkl[i][1];
  int l=1,r=1e5;
  while(l<r){
    int mid = l+r+1>>1;
    if(count(mid)<k) r=mid-1;
    else l = mid;
  }
  cout << l;
  return 0;
}