蓝桥杯2017省赛：分巧克力|枚举到二分

题目链接：

https://www.lanqiao.cn/problems/99/learning/?page=1&first_category_id=1&second_category_id=3&name=%E5%88%86%E5%B7%A7%E5%85%8B%E5%8A%9B

说明：

首先要注意题目的信息，要保证k个小朋友都至少获得一块1*1的巧克力，那么至少要分出 k块巧克力才行，这是作为二分的重要条件。并且注意要求：分出的每一块巧克力是大小相同的正方形，所以就是对n块巧克力的每个巧克力，都按同样的方式切。

能切出的巧克力总数：对于一块巧克力，能分出的正方形数量是（长/正方形边长） *（宽/正方形边长），必须长和宽分别除以，不能先长*宽 再除以 边长平方。因为能切出的数量必须是长和宽分别满足的最大数量相乘。比如1*8不能切出一块2*2的，如果按长*宽 再除以 边长平方就可以。

二分时需要注意的都写在注释了：当取l=mid，找边界最大值的时候，算mid的时候要+1，不然可能会出现死循环（当l=r-1时，条件为true）。除以2用右移代替提高效率。

再顺带一提，pair元素的访问方法：访问两个元素分别用.first，.second访问。

代码部分：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
typedef pair<int,int> pii; 
int n,k;//n块巧克力，k个朋友，至少要分出k块 
pii hw[N]; 
int ans=0;
int check(int x){
	int num=0;
	for(int i=0;i<n;i++){
//对于一块巧克力，能分出的正方形数量是（长/正方形边长） *（宽/正方形边长），必须分别除以
//因为必须满足长和宽都能分够相应的数量
		num+=((hw[i].first/x)*(hw[i].second/x));
    if(num>=k) return 1;
	}
   return 0;
}


signed main() {
   
   cin.tie(0);
   cout.tie(0);
   int mx=0;
   cin>>n>>k;
   for(int i=0;i<n;i++){
   	cin>>hw[i].first>>hw[i].second;
   	if(hw[i].first>mx) mx=hw[i].first;
   	if(hw[i].second>mx) mx=hw[i].second;
   }
 
   int r=mx,l=1;
//二分，注意当取l=mid，找边界最大值的时候，算mid的时候要+1，不然可能会出现死循环，
//当l=r-1时，不加一可能会死循环
   while(l<r){
   	int mid=(l+r+1)>>1;
   	if(check(mid)) l=mid;
   	else r=mid-1;
   }
   
   cout<<l;
   
    return 0;
}