【題解】Zerojudge h084 - 4. 牆上海報

題目連結

題目大意

有 $n$ 個木板，高度分別為 $h_1, \dots, h_n$。現在要貼上 $m$ 個水平的海報，寬度分別為 $w_1, \dots, w_m$。每個海報貼的高度要一致，不重疊且要貼在木板上。問最高可以貼到多高的位置？

• $1 \leq n \leq 2 \cdot 10^5$
• $1 \leq m \leq 5000$
• $1 \leq h_i \leq 10^9$
• $\sum w_i \leq n$

題解

觀察到答案具有單調性，也就是如果海報可以貼到高度為 $h$ 的話高度為 $h - 1$ 也可以 (看題目中的範例圖片會比較容易理解)。因此我們可以對答案進行二分搜，找到最高且滿足條件的位置。其他實作細節請參考 code。

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	vector<int> a(n);
	for(int i = 0; i < n; i++) {
		cin >> a[i];
	}
	vector<int> b(m);
	for(int i = 0; i < m; i++) {
		cin >> b[i];
	}
	auto f = [&](int height) {
		int len = 0;
		for(int i = 0, j = 0; i < n; i++) {
			if(a[i] >= height) {
				len++;
				if(len == b[j]) {
					len = 0;
					j++;
					if(j == m) {
						return true;
					}
				}
			} else {
				len = 0;
			}
		}
		return false;
	};
	int ok = 1, ng = 1E9 + 1;
	while(ng - ok > 1) {
		int mid = (ok + ng) / 2;
		if(f(mid)) {
			ok = mid;
		} else {
			ng = mid;
		}
	}
	cout << ok << "\n";
	return 0;
}

如果本文對您有幫助的話幫忙點擊廣告和分享吧！

© 若無特別註明，本站文章皆由 WeakMouse's Coding Blog 原創 ，轉載引用本文前請先留言告知。本文轉載請註明文章源自 WeakMouse's Coding Blog ，作者 ，並附上原文連結： 【題解】Zerojudge h084 - 4. 牆上海報