蓝桥杯2017年第八届真题-分巧克力(贪心，二分)

解题思路:
随着要求分的边长越来越大，可以分出的巧克力呈现非递增趋势，故而答案具有单调性，可以二分答案。

对于每一个要求的边长，采用贪心的办法求得此边长可以分出的巧克力个数，对于每一个巧克力来说，顺次分可以是答案为最优的一种实现办法，从行来看，正方形的上下顶点肯定处于相距一致的列中，那么我们安排这些正方形相邻是最优的情况，如果我们不这样做，在上下界空出若干行，可能导致部分可以放入的正方形无法放入。列也是类似的情况。故而直接采用行除以正方形边长和列除以边长算的分出最多巧克力个数。
注意事项:
r设置为所有边长中最大的，l为1。
参考代码:

#include<bits/stdc++.h>
using namespace std;
#define maxx 200000
int l,r,n,k;
int all1[maxx];
int all2[maxx];
int check(int x)
{
  int qq=0;
  for(int i=1;i<=n;++i)
  qq+=((all2[i]/x)*(all1[i]/x));
  if(qq>=k) return 1;
  else  return 0;
}
signed main()
{
  cin>>n>>k;
  for(int i=1;i<=n;++i)
  {cin>>all1[i]>>all2[i];
   r=max(all1[i],r);
   r=max(all2[i],r);}
   l=1;
  while(l<r)
  {
    int mid=(l+r)/2;
    if(check(mid)) l=mid+1;
    else  r=mid;
  }
  if(check(l)) cout<<l;
  else cout<<l-1;
}