h084 - 4. 牆上海報
題目描述
題目描述的是在一個由 $n$ 個木板組成的柵欄上張貼 $k$ 張海報的問題。每張海報有固定的寬度，且需要張貼在高度不小於某個值的連續木板上。目標是找到可以張貼所有海報的最高高度。
解題思路
本題採用二分搜的方法來尋找最大可張貼高度。對於一個給定的高度 $x$，我們需要判斷是否能夠在高度 $x$ 或以上張貼所有海報。判斷的方法是貪心算法：遍歷柵欄，記錄連續高度大於等於 $x$ 的木板數量，將其儲存在 ct 陣列中。然後，按照海報寬度順序，嘗試將每張海報張貼在 ct 陣列中足夠大的連續木板段上。如果所有海報都能成功張貼，則說明高度 $x$ 是可行的，否則不可行。二分搜的範圍是從 0 到柵欄中最高的木板高度。
複雜度分析
- 時間複雜度: O(n log(max_height))，其中 max_height 是柵欄中最高的木板高度。二分搜的複雜度是 O(log(max_height))，每次二分搜需要遍歷柵欄和海報，複雜度是 O(n + k)。由於 k <= 5000，可以視為常數，因此整體時間複雜度為 O(n log(max_height))。
- 空間複雜度: O(n + k)，主要用於儲存柵欄高度
a陣列，連續木板數量ct陣列和海報寬度b陣列。
程式碼
#include <iostream>
#include <set>
using namespace std;
int n,k,mah,a[200005],ct[200005],b[5005];
bool judge(int x){
int it=0,c=0,g=0;
for(int i=0;i<n;++i){
if(a[i]>=x){
++c;
}
else{
if(c){
ct[it++]=c;
c=0;
}
}
}
if(c){
ct[it++]=c;
c=0;
}
int i=0;
while(g<k){
if(ct[i]>=b[g]){
ct[i]-=b[g];
++g;
}
else{
++i;
if(i==it)return 0;
}
}
return 1;
}
int bs(int l,int r){
if(l>r)return r;
int m=(l+r)/2;
if(judge(m)) return bs(m+1,r);
return bs(l,m-1);
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
cin >> n >> k;
for(int i=0;i<n;++i){
cin >> a[i];
mah=max(a[i],mah);
}
for(int i=0;i<k;++i)
cin >> b[i];
cout << bs(0,mah);
}