牆上海報 題解｜APCS 2022 年 1 月高級 第 4 題

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;                                   // 這個子題組 k = 1
    vector<int> h(n);
    for (int &x : h) cin >> x;
    int w;
    cin >> w;
    int best = 0;
    for (int start = 0; start + w <= n; start++) {   // 海報從第 start 塊木板開始貼
        int lowest = h[start];                       // 這 w 塊木板裡最矮的那塊
        for (int i = start; i < start + w; i++) lowest = min(lowest, h[i]);
        best = max(best, lowest);
    }
    cout << best << '\n';
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int n, k;
vector<int> h, w;

bool canPost(int height) {                           // 全部海報都貼在高度 height，貼得完嗎
    int placed = 0, run = 0;                         // run：目前連續幾塊木板的高度 >= height
    for (int i = 0; i < n && placed < k; i++) {
        if (h[i] >= height) run++;
        else run = 0;                                // 太矮的木板把連續段切斷
        if (run == w[placed]) {                      // 湊滿目前這張海報的寬度：立刻貼上
            placed++;
            run = 0;                                 // 下一張從下一塊木板重新數
        }
    }
    return placed == k;
}

int main() {
    cin >> n >> k;
    h.resize(n);
    w.resize(k);
    for (int &x : h) cin >> x;
    for (int &x : w) cin >> x;
    int lo = 1, hi = *max_element(h.begin(), h.end());   // 高度 1 一定貼得完、超過最高木板一定不行
    while (lo < hi) {
        int mid = lo + (hi - lo + 1) / 2;            // 偏右取中點：找的是「最大的可行高度」
        if (canPost(mid)) lo = mid;                  // mid 貼得完：答案至少是 mid
        else hi = mid - 1;                           // 貼不完：答案比 mid 小
    }
    cout << lo << '\n';
    return 0;
}