當前位置:網站首頁>藍橋杯第三講--二分【習題】

藍橋杯第三講--二分【習題】

2022-01-27 11:20:03 辰chen

前言

藍橋杯官網:藍橋杯大賽——全國大學生TMT行業賽事
本博客講解 藍橋杯C/C++ 備賽所涉及算法知識,此博客為第三講:二分【習題】

二分算法的模板見博文:二分算法模板
二分【例題】詳見博客:藍橋杯第三講–二分【例題】

本篇博客所包含習題有:
機器人跳躍問題
四平方和
分巧克力

博客內容以題代講,通過講解題目的做法來幫助讀者快速理解算法內容,需要注意:學習算法不能光過腦,更要實踐,請讀者務必自己敲寫一遍本博客相關代碼!!!


機器人跳躍問題

本題來源:今日頭條2019,筆試題

題目要求

題目描述:

機器人正在玩一個古老的基於 DOS 的遊戲。

遊戲中有 N+1 座建築——從 0 到 N 編號,從左到右排列。

編號為 0 的建築高度為 0 個單比特,編號為 i 的建築高度為 H(i) 個單比特。

起初,機器人在編號為 0 的建築處。

每一步,它跳到下一個(右邊)建築。

假設機器人在第 k 個建築,且它現在的能量值是 E,下一步它將跳到第 k+1 個建築。

如果 H(k+1)>E,那麼機器人就失去 H(k+1)−E 的能量值,否則它將得到 E−H(k+1) 的能量值。

遊戲目標是到達第 N 個建築,在這個過程中能量值不能為負數個單比特。

現在的問題是機器人至少以多少能量值開始遊戲,才可以保證成功完成遊戲?

輸入格式:

第一行輸入整數 N。

第二行是 N 個空格分隔的整數,H(1),H(2),…,H(N) 代錶建築物的高度。

輸出格式:

輸出一個整數,錶示所需的最少單比特的初始能量值上取整後的結果。

數據範圍:

1 ≤ N, H(i) ≤ 105

輸入樣例1:

5
3 4 3 2 4

輸出樣例1:

4

輸入樣例2:

3
4 4 4

輸出樣例2:

4

輸入樣例3:

3
1 6 4

輸出樣例3:

3

思路分析

假設某一時刻(在第 k 個建築上的時候)能量為 E,且 H(k+1)>E,那麼在跳躍到第 k+1 個建築後,剩餘能量為:E-(H(k+1)−E)=2E-H(k+1);若有H(k+1)<E,那麼在跳躍到第 k+1 個建築後,剩餘能量為:E+(E−H(k+1))=2E-H(k+1)。綜上可以看出,不管 H(k+1) 和此時能量E有怎樣的關系,必然有在跳躍到 k+1 建築時有剩餘能量為:2E-H(k+1),不難知道,假設初始能量的最小值為 E0,那麼對於任何 Ei > E0,必然是可以跳到最後一個建築,故我們可以采用二分的做法,找到 E0,故我們可以設 l = 1,然後來考慮 r 的範圍,我們在跳躍的過程中要求自身的能量必須 >=0,那麼我們來找一找能量的上界:假設 hmax為 h數組中的最大值,那麼若此時的能量 E >= hmax,那麼就有 2E - hmax >= hmax,即我們的 E 如果一旦比 hmax 要大,就肯定滿足題目要求,故我們可以設 r = hmax.

代碼

#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 100010;

int h[N];
int n, hmax;

bool check(int e)
{
    
    for (int i = 0; i < n; i ++ ) 
    {
    
        e = 2 * e - h[i];
        if (e >= hmax) return true;
        if (e < 0) return false;
    }
    
    return true;
}

int main()
{
    
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) 
    {
    
        scanf("%d", &h[i]);
        if (hmax < h[i])
            hmax = h[i];
    }
        
    int l = 1, r = hmax;
    while (l < r)
    {
    
        int mid = l + r >> 1;   
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    
    printf("%d\n", l);
    
    return 0;
}

四平方和

本題來源:第七届藍橋杯省賽C++A/B組,第七届藍橋杯省賽JAVAB/C組

題目要求

題目描述:

四平方和定理,又稱為拉格朗日定理:

每個正整數都可以錶示為至多 4 個正整數的平方和。

如果把 0 包括進去,就正好可以錶示為 4 個數的平方和。

比如:
5=02+02+12+22
7=12+12+12+22

對於一個給定的正整數,可能存在多種平方和的錶示法。

要求你對 4 個數排序:
0 ≤ a ≤ b ≤ c ≤ d

並對所有的可能錶示法按 a,b,c,d 為聯合主鍵昇序排列,最後輸出第一個錶示法。

輸入格式:

輸入一個正整數 N。

輸出格式:

輸出4個非負整數,按從小到大排序,中間用空格分開。

數據範圍:

0 < N < 5 ∗106

輸入樣例:

5

輸出樣例:

0 0 1 2

思路分析1

藍橋杯嘛,又名“暴力杯”,這個題就很典型了,暴力運行速度比二分和哈希還快,離大譜,本題要求還是很直白的,唯一的地方就是在於要求按 a,b,c,d 為聯合主鍵昇序排列,即 a <= b <= c <= d,故我們在暴力枚舉的時候,a 從 0 開始枚舉,b 從 a 開始枚舉,c 從 b 開始枚舉,不需要枚舉 d,去判斷 d 是否合法即可,判斷 d 是否合法就是看 d 開平方後再平方是否和 d值一致,如果一致就輸出 a b c d 序列,並結束程序。

代碼1

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>

using namespace std;

int main()
{
    
    int n;
    scanf("%d", &n);
    
    for (int a = 0; a * a <= n; a ++ )
        for (int b = a; a * a + b * b <= n; b ++ ) 
            for (int c = b; a * a + b * b + c * c <= n; c ++ ) 
            {
    
                int t = n - (a * a + b * b + c * c);
                int d = sqrt(t);
                if (d * d == t)
                {
    
                    printf("%d %d %d %d\n", a, b, c, d);
                    exit(0);
                }
            }
            
    return 0;
}

思路分析2

我們對暴力進行優化,我們可以先枚舉兩維:枚舉 c 和 d,把 c 和 d 的所有情况全部存儲到一個數組之中(存儲 c2 + d2,c,d),然後再枚舉 a 和 b 的時候,計算 a2 + b2,對於每一個計算出來的 a2 + b2,我們都去數組中比對是否有一個c2 + d2使得 a2 + b2 + c2 + d2 = n,如果有,就輸出 a b c d 序列然後退出程序,因為我們要在數組中尋找是否有符合條件的c2 + d2,故我們可以給數組排序後二分查找,所以我們要重載小於號:重載規則為c2 + d2小的排在前面,然後在遍曆 a 和 b 之前給數組排序,現在我們還是來考慮 a <= b <= c <= d 這個問題,我們的 a 和 b可以在枚舉的時候采取暴力法中的那樣 a 從 0 開始,b 從 a 開始,且我們枚舉 c 和 d 按照暴力的方式同樣可以保證 c <= d,然後我們重載小於號時,可以讓 c2 + d2 的大小作為第一排序條件,然後按照 c 的大小排序,然後按照 d 的大小排序,這樣就可以保證 在 c2 + d2 相同的時候保證 c 更小的排在更前面。此時我們保證了 a<= b ,c <= d,現在來求證:b <= c:因為我們的 a 和 b 是從小到大進行枚舉的,且對於每一種情况我們都去判斷是否有符合條件的 c 和 d,因為 a2 + b2 + c2 + d2 = n,故在 a 和 b 都是很小數的情况下,要想 四平方和為以定值,c 和 d 必然是一個大數,即能保證 b <= c,證畢。

代碼2

#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 5000010;

struct Sum
{
    
    int s, c, d;
    bool operator < (const Sum &t) const
    {
    
        if (s != t.s) return s < t.s;
        if (c != t.c) return c < t.c;
        if (d != t.d) return d < t.d;
    }
}sum[N];

int main()
{
    
    int n;
    scanf("%d", &n);
    
    int m = 0;
    for (int c = 0; c * c <= n; c ++ ) 
        for (int d = c; c * c + d * d <= n; d ++ ) 
            sum[m ++] = {
    c * c + d * d, c, d};
            
    sort(sum, sum + m);
    
    for (int a = 0; a * a <= n; a ++ ) 
        for (int b = a; a * a + b * b <= n; b ++ )
        {
    
            int t = n - (a * a + b * b);
            int l = 0, r = m;
            while (l < r)
            {
    
                int mid = l + r >> 1;
                if (sum[mid].s >= t) r = mid;
                else l = mid + 1;
            }
            // 判斷一下是否真的找到了
            if (sum[l].s == t)
            {
    
                printf("%d %d %d %d\n", a, b, sum[l].c, sum[l].d);
                exit(0);
            }
        }
        
    return 0;
}

思路分析3

思路三其實就是思路二的另一種形式,我們思路二去查找的時候采取的是二分的查找方法,我們還可以采用哈希錶去查找,在將 {c2 + d2,c,d} 存入哈希錶前,判斷是否錶中已經有 c2 + d2 這樣的值,因為我們的 c 和 d 是從小到大枚舉的,因此先算到的 c2 + d2 肯定是優於後算到的 c2 + d2,哈希錶使用的是 C++ 中的庫,具體操作可查看博文:STL—map,unordered_map 和 map 用法是一致的,手寫哈希錶見博文:哈希錶

代碼3

注:藍橋杯官網不能使用 unordered_map,但是代碼思路無任何問題,正式比賽可以使用!

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <unordered_map>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

unordered_map<int, PII> res;

int main()
{
    
    int n;
    scanf("%d", &n);
    
    for (int c = 0; c * c <= n; c ++ )
        for (int d = c; c * c + d * d <= n; d ++ )
        {
    
            int t = c * c + d * d;
            if (!res.count(t))
                res[t] = {
    c, d};
        }
    
    for (int a = 0; a * a <= n; a ++ ) 
        for (int b = a; a * a + b * b <= n; b ++ ) 
        {
    
            int t = n - (a * a + b * b);
            if (res.count(t))
            {
    
                printf("%d %d %d %d\n", a, b, res[t].x, res[t].y);
                exit(0);
            }
        }
        
    return 0;
}

分巧克力

本題來源:第八届藍橋杯省賽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

思路分析

假設分得的正方形巧克力的邊長為 m,那麼對於一塊長為 Hi,寬為 Wi 的巧克力,其可以被分為:(Hi / m) * (Wi / m)塊,我們知道,分得巧克力的邊長和巧克力被拆成的塊數是成反比的,即邊長越長,分得的塊數越少,我們的目標是在可以分成 k 塊的前提下,使得邊長更大,故我們可以用二分求解

代碼

#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 100010;

int h[N], w[N];
int n, k;

bool check(int u)
{
    
    int sum = 0;
    for (int i = 0; i < n; i ++ ) 
    {
    
        int t = (h[i] / u) * (w[i] / u);
        sum += t;
        if (sum >= k) return true;
    }
    
    return false;
}

int main()
{
    
    scanf("%d%d", &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", l);
    
    return 0;
}

版權聲明
本文為[辰chen]所創,轉載請帶上原文鏈接,感謝
https://cht.chowdera.com/2022/01/202201271120024818.html

隨機推薦