藍橋杯學習記錄||1227. 分巧克力

AcWing||1227. 分巧克力

活動位址：https://www.acwing.com/activity/content/19/

考察要點：二分

題目要求

兒童節那天有 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

題目位址：https://www.acwing.com/problem/content/1229/

解析：每塊巧克力的長寬是不同的，是以需要建立一個二維數組進行存儲，切割為正方形的巧克力，是以我們隻需要枚舉 邊長 ，切割後是邊角是不能進行拼接的。

代碼思路 ：巧克力的邊長在1 ~ 105 之間 是以在區間内直接使用二分法，切割每個巧克力 塊（ 有效塊數 = (長/邊長) * (寬/邊長) ） 将每塊巧克力的有效快數加起來，若夠分，則二分 還可以向上取 即 l = mid 否則 r = mid - 1；

#include <iostream>
#include <cstring>
#include <algorithm>
 using namespace std;
 const int N = 1e5 + 10;
 int n, k, h[N], w[N];

bool check(int mid)
{
    int sum = 0;  //為有效巧克力塊數之和
    for (int i = 0; i < n; i ++ )          //對每塊巧克力進行切割
    {
        sum += h[i] / mid * (w[i] / mid);  //先除後乘 是以需要加括号
        if(sum >= k) return true;            //切割到每個人都有了 則傳回 true
    }
    return false;
}
 
int main()
{
    scanf("%d%d",&n, &k);              //n 塊巧克力 k 個人
    for (int i = 0; i < n; i ++ )
        scanf("%d%d", &h[i],&w[i]);
        
    int l = 1, r = 1e5;
    while (l < r)
    {
        int mid = l + r + 1 >> 1;      //向上取整 避免死循環
        if( check(mid) ) l = mid;      //如果夠分則邊長 可取大
        else r = mid - 1;             //不夠分 則取小
    }
    
    printf("%d\n",r);
    return 0;
}

           

本題:1227. 分巧克力

代碼參考:視訊講解