蓝桥杯真题 分巧克力 c++代码实现 分巧克力 儿童节那天有 K 位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。

蓝桥杯真题 分巧克力 c++代码实现 分巧克力 儿童节那天有 K 位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。

文章目录

• 题目描述
• 输入描述
• 输出描述
• 输入输出样例
• • 示例
• 运行限制
• 代码
• 思路

题目描述

儿童节那天有 K 位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。

小明一共有 N 块巧克力，其中第 i 块是 H_i ×W_i的方格组成的长方形。为了公平起见，小明需要从这 NN 块巧克力中切出 K 块巧克力分给小朋友们。切出的巧克力需要满足：

1.形状是正方形，边长是整数;

2.大小相同;

例如一块 6x5 的巧克力可以切出 6 块 2x2 的巧克力或者 2 块 3x3 的巧克力。

当然小朋友们都希望得到的巧克力尽可能大，你能帮小明计算出最大的边长是多少么？

输入描述

第一行包含两个整数 N,K (1≤N, K≤10⁵)。

以下 N 行每行包含两个整数 H_i ,W_i,(1 ≤ H_i, W_i ≤ 10⁵)。

输入保证每位小朋友至少能获得一块 1x1 的巧克力。

输出描述

输出切出的正方形巧克力最大可能的边长。

输入输出样例

示例

运行限制

最大运行时间：1s
最大运行内存: 256M

代码

#include <iostream>
#include <math.h>
using namespace std;
int main()
{int m, n;cin >> m >> n;int maxnum = 0;int* arr = new int[m];//动态申请内存int* arr1 = new int[m];for (int i = 0; i < m; i++){cin >> arr[i] >> arr1[i];maxnum = max(maxnum, arr[i]);//确定上限maxnum = max(maxnum, arr1[i]);}int si = 0;int l = 1;int r = maxnum;while(l<=r)//二分法查找，时间复杂度低{int mid = (l+r)/2;int num = 0;for (int j = 0; j < m; j++){num += (arr[j] / mid) * (arr1[j]/ mid);//每块巧克力在不同的边长的分法下得到的块数}if (num >= n)//满足每个人都能分到{l = mid + 1;si = mid;}else{r = mid-1;}}cout << si<<endl;return 0;
}

思路

使用了二分法查找的思想，可以减少运行的时间，主要是分析好巧克力的块数地计算部分。设一块巧克力的长度为m，宽度为n，要分成x边长的正方形，可得的块数为(m/x)×(n/x)，注意m，n应为int类型的数据，这样就可以保证计算的正确性，否则需要对上述计算式分别向下取整。明白了块数的计算方法之后只需要从1开始用二分法对计算就可以得出最大的边长。