分巧克力-蓝桥杯真题 二分查找(c++实现)

二进制诗人
• 阅读 158

上文链接:包子凑数-蓝桥杯真题 线性方程组求解(c++实现)


分巧克力

儿童节那天有K位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。
小明一共有N块巧克力,其中第i块是Hi x Wi的方格组成的长方形。
了公平起见,小明需要从这 N 块巧克力中切出K块巧克力分给小朋友们。切出的巧克力需要满足:

  1. 形状是正方形,边长是整数
  2. 大小相同

例如一块6x5的巧克力可以切出6块2x2的巧克力或者2块3x3的巧克力。
当然小朋友们都希望得到的巧克力尽可能大,你能帮小Hi计算出最大的边长是多少么?

输入

第一行包含两个整数N和K。(1 <= N, K <= 100000)
以下N行每行包含两个整数Hi和Wi。(1 <= Hi, Wi <= 100000)
输入保证每位小朋友至少能获得一块1x1的巧克力。

输出

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

样例输入:

2 10
6 5
5 6

样例输出:

2

资源约定:

峰值内存消耗(含虚拟机) < 256M

我的思路

  1. 由题可知:N块巧克力要切出K块巧克力(K块巧克力大小相同,要尽量大),所以该题可以从切割边长为100000到1对N个块进行二分查找切割(往往为了节省时间,查找使用二分,排序使用快排,因此本题采用二分查找),切割后记录切的总块数,满足大于K个块则解答成功。
  2. 蓝桥得分:87、运行超时、3.210,因此可以优化的地方是变量命名及变量取值。

算法展示

#include <iostream>
using namespace std;
int main()
{
    int K,N,His[100000],Wis[100000];
    cin>>N>>K;
    //输入 
    for(int i=0;i<N;i++)
    {
        cin>>His[i]>>Wis[i];
    } 
    //二分查找切割
    int high = 100000,low = 1,mid,count,ans;
    while(high>=low)
    {
        count = 0;
        mid = high/2+low/2;//防止溢出
        for(int i=0;i<N;i++)//对N个块进行切割 
        {
            count+=(His[i]/mid)*(Wis[i]/mid);
            /*等同于(Hi*Wi)>= K*mid*mid,如果是则将K记录到count.
            上句意思是某块面积是否大于可切块数cnt乘以当前最大切割边长对应面积,是则记录
            当前可切块数cnt.。  
            */ 
        }
        if(count>=K)
        {
            low = mid+1;//寻找切割边长更大值 
            ans = mid;    //记录目前合格的切割边长 
        }
        else high = mid-1; //寻找切割边长更小值 
    } 
    
    cout<<ans<<endl;
    return 0;
}
点赞
收藏
评论区
推荐文章
blmius blmius
4年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
Wesley13 Wesley13
3年前
MySQL部分从库上面因为大量的临时表tmp_table造成慢查询
背景描述Time:20190124T00:08:14.70572408:00User@Host:@Id:Schema:sentrymetaLast_errno:0Killed:0Query_time:0.315758Lock_
美凌格栋栋酱 美凌格栋栋酱
7个月前
Oracle 分组与拼接字符串同时使用
SELECTT.,ROWNUMIDFROM(SELECTT.EMPLID,T.NAME,T.BU,T.REALDEPART,T.FORMATDATE,SUM(T.S0)S0,MAX(UPDATETIME)CREATETIME,LISTAGG(TOCHAR(
Java修道之路,问鼎巅峰,我辈代码修仙法力齐天
<center<fontcolor00FF7Fsize5face"黑体"代码尽头谁为峰,一见秃头道成空。</font<center<fontcolor00FF00size5face"黑体"编程修真路破折,一步一劫渡飞升。</font众所周知,编程修真有八大境界:1.Javase练气筑基2.数据库结丹3.web前端元婴4.Jav
Wesley13 Wesley13
3年前
FLV文件格式
1.        FLV文件对齐方式FLV文件以大端对齐方式存放多字节整型。如存放数字无符号16位的数字300(0x012C),那么在FLV文件中存放的顺序是:|0x01|0x2C|。如果是无符号32位数字300(0x0000012C),那么在FLV文件中的存放顺序是:|0x00|0x00|0x00|0x01|0x2C。2.  
Wesley13 Wesley13
3年前
mysql设置时区
mysql设置时区mysql\_query("SETtime\_zone'8:00'")ordie('时区设置失败,请联系管理员!');中国在东8区所以加8方法二:selectcount(user\_id)asdevice,CONVERT\_TZ(FROM\_UNIXTIME(reg\_time),'08:00','0
Wesley13 Wesley13
3年前
PHP创建多级树型结构
<!lang:php<?php$areaarray(array('id'1,'pid'0,'name''中国'),array('id'5,'pid'0,'name''美国'),array('id'2,'pid'1,'name''吉林'),array('id'4,'pid'2,'n
Stella981 Stella981
3年前
Duang,HUAWEI DevEco IDE全面升级啦
想感受全新UI带来的视觉及交互体验、HiKey970开发板调测、HiAIAPI推荐和收藏、深度AI模型分析等新功能,体验高清晰度和流畅度的远程AI真机调测吗?!(https://oscimg.oschina.net/oscnet/f4e1bb24ff00b8c6ea27f75370a53bfbacd.jpg)全新的UI设计
Python进阶者 Python进阶者
1年前
Excel中这日期老是出来00:00:00,怎么用Pandas把这个去除
大家好,我是皮皮。一、前言前几天在Python白银交流群【上海新年人】问了一个Pandas数据筛选的问题。问题如下:这日期老是出来00:00:00,怎么把这个去除。二、实现过程后来【论草莓如何成为冻干莓】给了一个思路和代码如下:pd.toexcel之前把这
贾蔷 贾蔷
2个月前
蓝桥杯2023接龙数列(洛谷P9242)题解:动态规划与数字首尾匹配的完美应用
一、题目解读这道蓝桥杯省赛真题要求找出数字序列中最长的接龙子序列(每个数字的首位等于前一个数字的末位),并计算需要删除的最少数字个数。题目考察动态规划的实际应用能力,是理解数字特征处理和状态转移的典型案例。二、解题步骤1.处理n1的特殊边界情况2.读取输入
深度学习 深度学习
2个月前
2024年蓝桥杯国赛A组题 九宫格全解析:基于BFS算法的代码实现与优化
2024年蓝桥杯国赛A组题九宫格全解析:基于BFS算法的代码实现与优化蓝桥杯国赛九宫格问题BFS算法代码解析解题步骤第1张一、题目解读2024年蓝桥杯国A的九宫格题目(对应洛谷P10578)要求通过旋转九宫格中的2x2区域,实现从初始状态到目标状态的转换,
二进制诗人
二进制诗人
Lv1
莫愁前路无知己,天下谁人不识君。
文章
3
粉丝
0
获赞
0