大家好 我是寸鐵??

考前需要刷大量真題,大家一起相互監(jiān)督，每日做N題，一起上岸吧?? ~

第一期(二)

題目：分巧克力 ?

考點：二分 ??

該題目類型會同時收錄在相關(guān)復(fù)習(xí)專題，供大家學(xué)習(xí)

收錄??

藍橋杯上岸必背?。?！(持續(xù)更新中~)

不清楚藍橋杯考什么的點點下方??

考點秘籍

想背純享模版的伙伴們點點下方??

藍橋杯省一你一定不能錯過的模板大全(第一期)

藍橋杯省一你一定不能錯過的模板大全（第二期）

想背注釋模版的伙伴們點點下方??

藍橋杯必背第一期

藍橋杯必背第二期

往期精彩回顧

藍橋杯上岸每日N題 第一期(一)?。?！

操作系統(tǒng)期末題庫 第九期(完結(jié))

LeetCode Hot100 刷題(第三期)

idea創(chuàng)建SpringBoot項目報錯解決方案

數(shù)據(jù)庫SQL語句（期末沖刺）

想看JavaB組填空題的伙伴們點點下方 ??

填空題

二分

二分出答案！

怎么二分出答案？

這道題我們可以得出的是二分的結(jié)果是滿足k塊巧克力的最大邊長是多少？
題目要求：
1.形狀是正方形，邊長是整數(shù)
2.大小相同
即要求邊長均為x
我們就可以確保得到邊長一致的正方形
大小相同即分出的塊數(shù)為整數(shù)，向下取整?。?！
得到能夠湊出的整塊巧克力
如果分出的塊數(shù)有小數(shù)的大小肯定不同。

長、寬分別為H、W
塊數(shù)：(H/x)*(W/x)

為什么是這么多塊？

相同的x下
我們可以發(fā)現(xiàn)長為H
可以被切成H/x塊
我們可以發(fā)現(xiàn)寬為W
可以被切成W/x塊
這么多塊的組合起來為(H/x)*(W/x)這么多塊

那我們推出這個公式后，我們怎么利用二分來處理這道題？

我們知道二分一般情況下需要具有二段性/單調(diào)性
即確定一個mid后，兩邊是否具有二段性/單調(diào)性
假設(shè)k=(H/x)*(W/x)
我們根據(jù)公式發(fā)現(xiàn)(H/x)*(W/x)中H、W是常量。
x是變量,且隨著x的增大,k值是越來越小的。
而隨著x的減小,k值是越來越大的。
中間必定存在k使得x最大
這即是我們需要的二段性。
畫出圖形應(yīng)該是單調(diào)遞減的曲線
x是我們要二分的答案

更進一步我們可以發(fā)現(xiàn)
假設(shè)我們在x的條件下剛好二分出k塊的巧克力。
由上證明,比x小的也一定滿足可以條件,可以分出大于k塊巧克力。
我們讓l右移讓他往右邊去找,k塊巧克力下邊長盡可能的大
即l=mid;
比x大的一定不滿足條件，不足以分出k塊巧克力。
我們讓r左移讓他往左邊去找,k塊巧克力下邊長盡可能的大
即r=mid-1;

二分出的k塊巧克力下的x必定是滿足k塊的最大邊長！?。?/h3>

Accode

import java.util.*;
public class Main{
    static int N=100010;
    static int cake[][]=new int[N][2];
    //輸入是N行2列
    //不要開N行N列用不到的空間會MLE
    static int n,m,k;
    public static void main(String []args){
        Scanner sc=new Scanner(System.in);
         n=sc.nextInt();
         k=sc.nextInt();        
        for(int i=0;i<n;i++){
            cake[i][0]=sc.nextInt();
            cake[i][1]=sc.nextInt();
        }
        //答案確保所得至少1*1
        //邊長最小為1
        //二分的左邊界為1
        //右邊界為最大邊長1e5
        int l=1;
        int r=(int)1e5;
        while(l<r){
            int mid=l+r+1>>1;
            if(check(mid))l=mid;
            //mid下的塊>=k則l右移l=mid
            //注意mid是滿足>=k所以是l=mid
            
            //與之對應(yīng)的是r=mid-1
            //因為此時check(mid)<k
            //所以需要往左移且mid不滿足條件
            //所以r=mid-1
            else r=mid-1;
        }
        System.out.println(l);
    }
    public static boolean check(int m){
        int res=0;
        for(int i=0;i<n;i++){
            res+=(cake[i][0]/m)*(cake[i][1]/m);
        //統(tǒng)計能分出的塊數(shù)
        }
        //塊數(shù)>=k說明是需要將邊長邊大塊數(shù)減少
        //即l=mid;
        if(res>=k)return true;
        //反之則說明不足k塊需要將邊長減小塊數(shù)增大
        //即r=mid-1
        return false;
    }
}

????????????
后續(xù)有補充，持續(xù)更新中??
喜歡的伙伴點點贊，關(guān)個注??文章來源地址http://www.zghlxwxcb.cn/news/detail-579504.html

到了這里，關(guān)于藍橋杯上岸每日N題第一期(二)?。?！的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！