蓝桥杯:二分法求分巧克力

简介: 蓝桥杯:二分法求分巧克力

来源:第八届蓝桥杯省赛C++A/B组,第八届蓝桥杯省赛JAVAA/B组

题目描述:

儿童节那天有 K 位小朋友到小明家做客。

小明拿出了珍藏的巧克力招待小朋友们。


小明一共有 N 块巧克力,其中第 i 块是 Hi×Wi 的方格组成的长方形。


为了公平起见,小明需要从这 N 块巧克力中切出 K 块巧克力分给小朋友们。


切出的巧克力需要满足:


1.形状是正方形,边长是整数


2.大小相同


例如一块 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

#include<iostream>
#include<cstdio>
using namespace std;
int n, k;
int h[100050], w[100050];
int check(int mid)
{
    int i, res = 0;
    for (i = 0; i < n; i++)
    {
        res += (h[i] / mid) * (w[i] / mid);
        if (res >= k) return  1;
    }
    return 0;
}
int main()
{
    cin >> n >> k;
    int i;
    for (i = 0; i < n; i++)
    {
        scanf("%d %d", &h[i], &w[i]);
    }
    int l = 1, r = 100000;
    while (l < r)
    {
        int mid = (l + r + 1) / 2;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    cout << l << endl;
    return 0;
}


目录
相关文章
|
算法 测试技术 Python
第十二届蓝桥杯《杨辉三角》-二分法
第十二届蓝桥杯《杨辉三角》-二分法
101 0
|
算法 测试技术
蓝桥杯2022年第十三届决赛真题-卡牌——二分法
蓝桥杯2022年第十三届决赛真题-卡牌——二分法
129 0
|
编译器 C++ Python
蓝桥杯 分巧克力 python
蓝桥杯 分巧克力 python
蓝桥杯分巧克力(暴力枚举解法+二分法)
问题 F 时间限制: 1Sec 内存限制: 128MB 提交: 66 解决: 28
|
7月前
|
人工智能 算法 Java
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-992 士兵杀敌(二)
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-992 士兵杀敌(二)
89 1
|
7月前
|
人工智能 算法 Java
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1005 数字游戏
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1005 数字游戏
111 0
|
7月前
|
Java C语言 C++
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1000 kAc给糖果你吃
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1000 kAc给糖果你吃
86 0
|
7月前
|
算法 Java C语言
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-999 数的潜能
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-999 数的潜能
91 0
|
7月前
|
算法 Java C语言
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-997 粘木棍
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-997 粘木棍
95 0
|
7月前
|
机器学习/深度学习 算法 Java
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-996 车的放置
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-996 车的放置
95 0