zerojudge網址 https://zerojudge.tw/ShowProblem?problemid=h084
有一個由n個木板所組成的柵欄,每個木板的高度為h[1],h[2],...,h[n] ,有 k張海報要張貼在柵欄上,每張海報的寬度為w[1],w[2],...,w[k]並且高度均為1。
若要張貼海報在高度為x的高度,則第i 張海報需要張貼在一個寬度為w[i]的連續並且高度都不小於x的木板上,且每張海報張貼的高度需要一致、按照順序並不能重疊 (可以相連)。詢問最高可以貼到多高的位置。
輸入說明
第一行有兩個正整數n,k,接下來一行有 n個正整數代表每個木板的高度,最後一行有k個正整數代表每張海報的寬度。
數字範圍
1 <= n <=200000
1<=k<=5000
1<=h[i]<=10^9
w[1]+w[2]+..+w[k]<=n
輸出說明
輸入最大可以張貼的高度
輸入範例
5 1
6 3 7 5 1
3
10 3
5 3 7 5 1 7 5 3 8 4
2 2 1
輸出範例
3
5
解題策略:二分搜尋
自訂函式iswork,高度為x,能否將所有海報貼上,可以則回傳true,否則回傳false。使用二分搜尋先從柱子最高(R)與最低(L)取一半到變數(M),呼叫函式iswork以M為輸入進行判斷,若此高度M可以貼上,將最低(L)設定為M,否則最高(R)設定為M-1,再取最高(R)與最低(L)取一半到變數(M),繼續呼叫iswork以M為輸入進行判斷。