h084: 4. 牆上海報

2022.12.15 PM 09:00 by CBJ

來源 : https://zerojudge.tw/ShowProblem?problemid=h084
出題者 : 2022年1月APCS
標籤 : 二分搜尋法、貪心法
難易度 : 4

解題想法 : 
想出要如何實作是這題最難的地方，只要(通靈)想出要用二分搜尋，這題就很好解了。

觀察題目測資大小，可以發現n的最大值是2*10^5，因此可以使用O(NlogN)的演算法，首先可以確定二分搜的複雜度是O(logN)，那麼剩下的N就可以留給循序檢查高度使用，簡單的一個一個爬過去就好。

那要搜什麼？
這題的單調性在於，假如在高度為x的地方能夠貼完海報，那麼比x小的高度也一定可以貼(畫圖應該就可以理解)，畢竟沒有中間破洞的木板，因此對於每次的x，都可以縮減高度的範圍，符合二分搜的單調性質。

再來就是檢查高度為x時，是否有辦法貼完海報，實作上可以定義一個函式check(x)，從左數到右，每遇到一塊木板，寬度就+1，只要累積寬度等於要放的海報寬時，就把成功次數+1，並將累積寬度歸零，同時海報要換成下一張來貼(由於題目有規定要「按照順序貼」，所以就可以利用貪心法的原則，遇到夠寬的就貼下去。)，最後只需要判斷成功次數是否等於海報的數量即可判斷是否成功貼完所有海報。

## C++ language

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int n,k; 
vector<int>high,width;
bool check(int m){
    int cnt=0,idx=0,success=0;
    for(int i:high){
        if(idx==k) break;
        if(i>=m) cnt++;
        else{cnt=0;continue;}
        if(cnt==width[idx]){
            success++;
            idx++;
            cnt=0;
        }
    }
    return (success==k);
}
int main(){
    cin>>n>>k;
    high.resize(n); width.resize(k);
    for(int &i:high) cin>>i;
    for(int &i:width) cin>>i;
    
    int L=-1,R=*max_element(high.begin(),high.end())+1;
    while(R-L>1){
        int m=(L+R)/2;
        if(check(m)) L=m;
        else R=m;
    }
    
    cout<<L<<"\n";
    return 0;
}

## Python language

n,k=map(int,input().split())
high=[int(x) for x in input().split()]
width=[int(x) for x in input().split()]
def check(m):
    cnt=idx=success=0
    for i in high:
        if idx==k: break
        if i>=m: cnt+=1
        else:
            cnt=0
            continue
        if cnt==width[idx]:
            success+=1
            idx+=1
            cnt=0
    if success==k: return True
    return False
maxh=max(high)
L=-1; R=maxh+1
while R-L>1:
    m=L+(R-L)//2
    if(check(m)): L=m
    else: R=m
print(L)

相關文章

分享此文：