# APCS實作題2022年1月第4題：牆上海報

> 第1版：2024年8月15日
> 第2版：2024年12月15日，新增跳躍二分搜尋法程式碼
> 作者：王一哲
> [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=h084)

## 題目

### 問題描述

有一個由 $n$ 個木板所組成的柵欄，每個木板的高度為 $h_1, h_2, \dots, h_n$，有 $k$ 張海報要張貼在柵欄上，每張海報的寬度為 $w_1, w_2, \dots, w_n$ 並且高度均為 $1$。

若要張貼海報在高度為 $x$ 的高度，則第 $i$ 張海報需要張貼在一個寬度為 $w_i$ 的連續並且高度都不小於 $x$ 的木板上，且每張海報張貼的**高度需要一致、按照順序並不能重疊**，可以相連。詢問最高可以貼到多高的位置。
<br />

### 輸入說明

第一行有兩個正整數 $n, k$，接下來一行有 $n$ 個正整數代表每個木板的高度，最後一行有 $k$ 個正整數代表每張海報的寬度。

數字範圍
- $1 \leq n \leq 200000$
- $1 \leq k \leq 5000$
- $1 \leq h_i \leq 10^9$
- $\sum w_i \leq n$

子題配分
- 20%：$1 \leq n \leq 100,~ k = 1$
- 40%：$k = 1$
- 40%：無額外限制

<br />

### 輸出格式

輸入最大可以張貼的高度。
<br />

### 範例輸入1

5 1
6 3 7 5 1
3

### 範例輸出1

3

### 範例輸入2

10 3
5 3 7 5 1 7 5 3 8 4
2 2 1

### 範例輸出2

5

<br /><br />

## Python 程式碼

### 寫法1，二分搜尋法

費時最久約為 1.3 s，使用記憶體最多約為 28.5 MB，通過測試。

n, k = map(int, input().split())  # 讀取牆壁數量 n、海報數量 k
hs = list(map(int, input().split()))  # 讀取牆壁高度
ws = list(map(int, input().split()))  # 讀取海報寬度

def check(m):  # 自訂函式，檢測指定高度是否能貼所有的海報
    i = 0  # 讀取海報寬度的索引值
    width = 0  # 連繼牆壁寬度
    for h in hs:  # 依序由 hs 讀取高度 h
        if h >= m: width += 1  # 如果這片牆壁高度大於等於 m，width 加 1
        else: width = 0; continue  # 否則將 width 歸零，找下一片
        if width == ws[i]:  # 如果 width 等於目前的海報寬度
            i += 1; width = 0  # i 加 1，width 歸零
        if i == k: return True  # 如果 i 等於 k，所有海報都能貼上，回傳 True
    return False  # 如果離開 for 迴圈，表示有海報無法貼上，回傳 False

low, high = 1, 1000000001  # 可能的答案最小值、最大值
while low <= high:  # 繼續執行的條件
    mid = (high - low) // 2 + low  # 中間值
    if check(mid): low = mid  # 如果 mid 符合要求，提高 low，找更高的高度
    else: high = mid  # 否則降低 high，找更低的高度

print(low)  # 輸出答案 low

<br />

如果改成 [low, high] 閉區間的寫法，答案會存在變數 high。費時最久約為 1.3 s，使用記憶體最多約為 28.5 MB，通過測試。

n, k = map(int, input().split())  # 讀取牆壁數量 n、海報數量 k
hs = list(map(int, input().split()))  # 讀取牆壁高度
ws = list(map(int, input().split()))  # 讀取海報寬度

def check(m):  # 自訂函式，檢測指定高度是否能貼所有的海報
    i = 0  # 讀取海報寬度的索引值
    width = 0  # 連繼牆壁寬度
    for h in hs:  # 依序由 hs 讀取高度 h
        if h >= m: width += 1  # 如果這片牆壁高度大於等於 m，width 加 1
        else: width = 0; continue  # 否則將 width 歸零，找下一片
        if width == ws[i]:  # 如果 width 等於目前的海報寬度
            i += 1; width = 0  # i 加 1，width 歸零
        if i == k: return True  # 如果 i 等於 k，所有海報都能貼上，回傳 True
    return False  # 如果離開 for 迴圈，表示有海報無法貼上，回傳 False

low, high = 1, 1000000001  # 可能的答案最小值、最大值
while low <= high:  # 繼續執行的條件
    mid = (high - low) // 2 + low  # 中間值
    if check(mid): low = mid+1  # 如果 mid 符合要求，提高 low，找更高的高度
    else: high = mid-1  # 否則降低 high，找更低的高度

print(high)  # 輸出答案 high

<br />

### 寫法2，跳躍二分搜尋法

費時最久約為 1.4 s，使用記憶體最多約為 27.7 MB，通過測試。

n, k = map(int, input().split())  # 讀取牆壁數量 n、海報數量 k
hs = list(map(int, input().split()))  # 讀取牆壁高度
ws = list(map(int, input().split()))  # 讀取海報寬度

def check(m):  # 自訂函式，檢測指定高度是否能貼所有的海報
    i = 0  # 讀取海報寬度的索引值
    width = 0  # 連繼牆壁寬度
    for h in hs:  # 依序由 hs 讀取高度 h
        if h >= m: width += 1  # 如果這片牆壁高度大於等於 m，width 加 1
        else: width = 0; continue  # 否則將 width 歸零，找下一片
        if width == ws[i]:  # 如果 width 等於目前的海報寬度
            i += 1; width = 0  # i 加 1，width 歸零
        if i == k: return True  # 如果 i 等於 k，所有海報都能貼上，回傳 True
    return False  # 如果離開 for 迴圈，表示有海報無法貼上，回傳 False

h, jump = 1, (1+1000000001)//2  # 可能的答案、跳躍距離
while jump:  # 當 jump 大於 0 時繼續執行
    if check(h+jump): h += jump  # 如果 h+jump 符合要求，提高 h，找更高的高度
    else: jump >>= 1  # 反之代表跳躍距離太遠，jump 減半
# 結束 while 迴圈時，h 為答案
print(h)  # 輸出答案

<br /><br />

## C++ 程式碼

### 寫法1，二分搜尋法

費時最久約為 35 ms，使用記憶體最多約為 2.6 MB，通過測試。

#include <iostream>
#include <vector>
using namespace std;

bool check(int m, vector<int> hs, vector<int> ws) {  // 自訂函式，檢測指定高度是否能貼所有的海報
    int width = 0, i = 0;  // 連繼牆壁寬度 width，讀取海報寬度的索引值 i
    for(int h : hs) {  // 依序由 hs 讀取高度 h
        if (h >= m) {  // 如果這片牆壁高度大於等於 m，width 加 1
            width++;
        } else {  // 否則將 width 歸零，找下一片
            width = 0;
            continue;
        }
        if (width == ws[i]) {  // 如果 width 等於目前的海報寬度
            i++; width = 0;  // i 加 1，width 歸零
        }
        if (i == (int)ws.size()) return true;  // 如果 i 等於 k，所有海報都能貼上，回傳 true
    }
    return false;  // 如果離開 for 迴圈，表示有海報無法貼上，回傳 false
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, k; cin >> n >> k;  // 讀取牆壁數量 n、海報數量 k
    vector<int> hs (n), ws (k);
    for(int i=0; i<n; i++) cin >> hs[i];  // 讀取牆壁高度
    for(int i=0; i<k; i++) cin >> ws[i];  // 讀取海報寬度
    
    int low = 0, high = 1000000001;  // 可能的答案最小值、最大值
    while(high - low > 1) {  // 繼續執行的條件
        int mid = (high - low) / 2 + low;  // 中間值
        if (check(mid, hs, ws)) low = mid;  // 如果 mid 符合要求，提高 low，找更高的高度
        else high = mid;  // 否則降低 high，找更低的高度
    }
    cout << low << "\n";  // 輸出答案 low
    return 0;
}

<br />

如果改成 [low, high] 閉區間的寫法，答案會存在變數 high。費時最久約為 48 ms，使用記憶體最多約為 2.6 MB，通過測試。

#include <iostream>
#include <vector>
using namespace std;

bool check(int m, vector<int> hs, vector<int> ws) {  // 自訂函式，檢測指定高度是否能貼所有的海報
    int width = 0, i = 0;  // 連繼牆壁寬度 width，讀取海報寬度的索引值 i
    for(int h : hs) {  // 依序由 hs 讀取高度 h
        if (h >= m) {  // 如果這片牆壁高度大於等於 m，width 加 1
            width++;
        } else {  // 否則將 width 歸零，找下一片
            width = 0;
            continue;
        }
        if (width == ws[i]) {  // 如果 width 等於目前的海報寬度
            i++; width = 0;  // i 加 1，width 歸零
        }
        if (i == (int)ws.size()) return true;  // 如果 i 等於 k，所有海報都能貼上，回傳 true
    }
    return false;  // 如果離開 for 迴圈，表示有海報無法貼上，回傳 false
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, k; cin >> n >> k;  // 讀取牆壁數量 n、海報數量 k
    vector<int> hs (n), ws (k);
    for(int i=0; i<n; i++) cin >> hs[i];  // 讀取牆壁高度
    for(int i=0; i<k; i++) cin >> ws[i];  // 讀取海報寬度
    
    int low = 0, high = 1000000001;  // 可能的答案最小值、最大值
    while(low <= high) {  // 繼續執行的條件
        int mid = (high - low) / 2 + low;  // 中間值
        if (check(mid, hs, ws)) low = mid+1;  // 如果 mid 符合要求，提高 low，找更高的高度
        else high = mid-1;  // 否則降低 high，找更低的高度
    }
    cout << high << "\n";  // 輸出答案
    return 0;
}

<br />

### 寫法2，跳躍二分搜尋法

費時最久約為 37 ms，使用記憶體最多約為 2.6 MB，通過測試。

#include <iostream>
#include <vector>
using namespace std;

bool check(int m, vector<int> hs, vector<int> ws) {  // 自訂函式，檢測指定高度是否能貼所有的海報
    int width = 0, i = 0;  // 連繼牆壁寬度 width，讀取海報寬度的索引值 i
    for(int h : hs) {  // 依序由 hs 讀取高度 h
        if (h >= m) {  // 如果這片牆壁高度大於等於 m，width 加 1
            width++;
        } else {  // 否則將 width 歸零，找下一片
            width = 0;
            continue;
        }
        if (width == ws[i]) {  // 如果 width 等於目前的海報寬度
            i++; width = 0;  // i 加 1，width 歸零
        }
        if (i == (int)ws.size()) return true;  // 如果 i 等於 k，所有海報都能貼上，回傳 true
    }
    return false;  // 如果離開 for 迴圈，表示有海報無法貼上，回傳 false
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, k; cin >> n >> k;  // 讀取牆壁數量 n、海報數量 k
    vector<int> hs (n), ws (k);
    for(int i=0; i<n; i++) cin >> hs[i];  // 讀取牆壁高度
    for(int i=0; i<k; i++) cin >> ws[i];  // 讀取海報寬度
    
    int h = 1, jump = (1+1000000001)/2;  // 可能的答案、跳躍距離
    while(jump) {  // 如果 jump 大於 0 繼續執行的條件
        if (check(h+jump, hs, ws)) h += jump;  // 如果 h+jump 符合要求，提高 h，找更高的高度
        else jump >>= 1;  // 反之代表跳躍距離太遠，jump 減半
    }
    cout << h << "\n";  // 輸出答案
    return 0;
}

<br /><br />

---

###### tags:`APCS`、`Python`、`C++`