本文主要是介绍蓝桥杯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;
}这篇关于蓝桥杯2017省赛：分巧克力|枚举到二分的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
