[数据结构与算法]蓝桥杯真题：分巧克力

?

我们要求出满足条件的大的边长m。

首先我们知道最长的边长是100000，最小的边长是1，那么我们可以来二分，最初设l=1,r=100000

之后进行如下操作：

1.求中点位置mid=(l+r)/2

2.对边长mid记录每个巧克力可以分成多少块，容易想到分成的块数=(长/mid)*(宽/mid)

3.

• 总块数<k，说明边mid大了，我们要往小的去找,r=mid-1
• 否则，边长是满足条件的，我们要l=mid+1去找是否存在更大的边长满足总块数>=k

#include <iostream>
using namespace std;
const int N=100005;
int n,k,ans;
int chok[N][2];
int main()
{
  // 请在此输入您的代码
  cin>>n>>k;
  for(int i=0;i<n;++i)
  {
    cin>>chok[i][0]>>chok[i][1];
  }
  int l=1,r=100000;

  while(l<=r)
  {
    int mid=(l+r)/2;
    int num=0;
    for(int i=0;i<n;++i)
    {
      num+=(chok[i][0]/mid)*(chok[i][1]/mid);
    }
    if(num>=k)
    {
      if(mid>ans)
      {
        ans=mid;
      }
      l=mid+1;
    }
    else
    {
      r=mid-1;
    }
  }
  cout<<ans<<endl;
  return 0;
}

还有一种取巧的暴力解法碰巧过了，就是设一个长度是10000的边递减去测试，好像测试里边没有比10000的更小的边：

#include <iostream>
using namespace std;
const int N=100005;
int n,k;
int chok[N][2];
int main()
{
  // 请在此输入您的代码
  cin>>n>>k;
  for(int i=0;i<n;++i)
  {
    cin>>chok[i][0]>>chok[i][1];
  }
  int m=10000;
  while(true)
  {
    int sum=0,n1,n2;
    for(int i=0;i<n;++i)
    {
      n1=chok[i][0]/m;
      n2=chok[i][1]/m;
      sum+=n1*n2;
    }
    if(sum>=k)
    {
      break;
    }
    m--;
  }
  cout<<m<<endl;
  return 0;
}