分巧克力（蓝桥杯） |
您所在的位置：网站首页 › 请问巧克力 › 分巧克力（蓝桥杯） |
分巧克力（蓝桥杯）
|
文章目录
分巧克力题目描述二分算法
分巧克力
题目描述
儿童节那天有 K位小朋友到小明家做客。 小明拿出了珍藏的巧克力招待小朋友们。 小明一共有 N块巧克力，其中第 i 块是 Hi×Wi 的方格组成的长方形。 为了公平起见，小明需要从这 N 块巧克力中切出 K 块巧克力分给小朋友们。 切出的巧克力需要满足： 形状是正方形，边长是整数大小相同 例如一块 6×5 的巧克力可以切出 6块 2×2 的巧克力或者 2 块 3×3的巧克力。 当然小朋友们都希望得到的巧克力尽可能大，你能帮小明计算出最大的边长是多少么？输入格式 第一行包含两个整数 N 和 K。 以下 N行每行包含两个整数 Hi和 Wi。 输入保证每位小朋友至少能获得一块 1×1 的巧克力。 输出格式 输出切出的正方形巧克力最大可能的边长。 数据范围 1≤N,K≤105, 1≤Hi,Wi≤105 输入样例： 2 10 6 5 5 6输出样例： 2 二分算法如果看不懂题目要求，画图就可以理解了，如下图： 如何判断怎么从检查是否能从所有巧克力块中切出至少k块边长为z的正方形巧克力？ 从上图可以看出，切割的块数=h/mid * w/mid。例如5 * 6的巧克力，能切割出的块数=5/2 * 6/2=2 * 3=6。 ps：在求r时我刚开始做的时候求的是所有巧克力的最小边，但这样子是不对的，因为当总巧克力足够多时，例如100块，里面的数据可能会有2 * 3的小巧克力，甚至1 * 1的小巧克力，这样的数据可以舍去，并不影响求输出切出的正方形巧克力，所以r的值应该为最大巧克力的最小边（所有巧克力的最小边长） #include // 包含C++标准库的所有头文件 using namespace std; // 声明全局变量 int n, k, h[100010], w[100010]; // n为巧克力数量, k为小朋友数量, h和w分别存储每块巧克力的高和宽 // 检查是否能从所有巧克力块中切出至少k块边长为z的正方形巧克力 bool check(int z) { int count = 0; // 用于计算能切出的正方形巧克力的个数 for (int i = 0; i = k) return true; // 如果已经能切出至少k块，则返回true } return false; // 如果不能切出至少k块，则返回false } int main() { cin >> n >> k; // 输入巧克力的数量和小朋友的数量 int i; int max_size = 0; // 存储所有巧克力中最长的边 for (i = 0; i > h[i] >> w[i]; // 输入每块巧克力的高和宽 max_size = max(max_size, min(h[i], w[i])); //最大巧克力的最小边 } //二分查找——右查找：找最大值 int l = 1, r = max_size; // 设置二分搜索的范围 while (l > 1; // 计算中间值，向上取整 if (check(mid)) l = mid; // 如果能切出足够多的巧克力，则向右收缩范围 else r = mid - 1; // 如果不能切出足够多的巧克力，则向左收缩范围 } cout |
如果使用二分算法，那么切割的巧克力边长依题意最小为1，最大为最大巧克力的最小边，因此l=1,r=最大巧克力的最小边，因为要求出输出切出的正方形巧克力最大可能的边长，所以使用二分查找中的右查找得到最大值。【本文地址】