[数据结构与算法]蓝桥杯省赛真题 分巧克力（暴力/二分）

?该题有两种方法可解

总体来说我们的思路就是，枚举切出的正方形巧克力边长，然后分别用我们所拥有的巧克力的长和宽来除以我们的枚举边长，得到的二者相乘我们就能得到该块巧克力能分出的该种边长的块数了，直到我们找到最大的能分出的巧克力块数即可break了

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
typedef unsigned long long ll;
const int MAXN = 100005;
int check[MAXN] = { 0 };
int cholo[MAXN][2];
int main()
{
    int n, k, H, W;
    cin >> n >> k;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < 2; j++)
        {
            cin >> cholo[i][j];
        }
    }
    for (int i = 1; i < MAXN - 5; i++)//枚举切出的巧克力边长
    {
        int sum = 0;//记得重新初始化sum
        for (int j = 0; j < n; j++)//枚举我们手里的巧克力
        {
            sum += ((cholo[j][0] / i) * (cholo[j][1] / i));
            if (sum >= k)//小优化 如果已经大于k ，就直接break
            {
                check[i] = 1;
                break;
            }
        }
        if (sum >= k)//如果这个边长可以的话依此为数组下标记录下来
        {
            check[i] = 1;
        }
        else//不可以了就break
        {
            break;
        }
    }
    for (int i = 1; i < MAXN; i++)
    {
        if (check[i] == 0)//找到第一个不可以的边长
        {
            cout << i - 1 << endl;//
            break;
        }
    }
    return 0;
}

实际上，对于这种我们需要枚举什么东西（暴力）的时候，我们需要培养一种使用二分查找算法的意识，这样可以避免 n^2 的时间复杂度

下面是结合了二分查找算法的代码，实际上，思路与上面的代码是一样的，不过将第一层枚举换成了二分查找而言

#include<iostream>//二分查找
#include<vector>
#include<queue>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
typedef unsigned long long ll;
const int MAXN = 100005;
int cholo[MAXN][2];

int main()
{
	int n, k,ans=0;
	cin >> n >> k;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < 2; j++)
		{
			cin >> cholo[i][j];
		}
	}
	int l = 1, r = 100000;
	while (l <= r)
	{
		int sum = 0;
		int mid = (r + l) / 2;
		for (int i = 0; i < n; i++)
		{
			sum += ((cholo[i][0] / mid) * (cholo[i][1] / mid));
		}
		if (sum >= k)
		{
			if (mid > ans)
			{
				ans = mid;
			}
			l = mid + 1;
		}
		if(sum<k)
		{
			r = mid - 1;
		}
	}
	cout << ans << endl;
	return 0;
}

?