h084: 4. 牆上海報
Tags : APCS 二分搜 貪心法
Accepted rate : 258人/309人 ( 83% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-01-13 08:59

Content

有一個由 $n$ 個木板所組成的柵欄,每個木板的高度為 $h[1], h[2], ..., h[n]$,有 $k$ 張海報要張貼在柵欄上,每張海報的寬度為 $w[1], w[2], \cdots, w[n]$ 並且高度均為 $1$。

若要張貼海報在高度為 $x$ 的高度,則第 $i$ 張海報需要張貼在一個長度為 $w[i]$ 的連續並且高度都不小於 $x$ 的木板上,且每張海報張貼的高度需要一致、按照順序並不能重疊 (可以相連)。詢問最高可以貼到多高的位置。

Input

第一行有兩個正整數 $n, k$,接下來一行有 $n$ 個正整數代表每個木板的高度,最後一行有 $k$ 個正整數代表每張海報的寬度。

 

數字範圍

  • $1 \leq n \leq 200000$
  • $1 \leq k \leq 5000$
  • $1 \leq h_i \leq 10^9$
  • $\sum w_i \leq n$

子題配分

  • (20%): $1\leq n \leq 100, k=1$
  • (40%): $k=1$
  • (40%): 無額外限制
Output

輸入最大可以張貼的高度。

Sample Input #1
5 1
6 3 7 5 1
3
Sample Output #1
3
Sample Input #2
10 3
5 3 7 5 1 7 5 3 8 4
2 2 1
Sample Output #2
5
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (5%): 2.0s , <1K
公開 測資點#1 (5%): 2.0s , <1K
公開 測資點#2 (5%): 2.0s , <1K
公開 測資點#3 (5%): 2.0s , <1K
公開 測資點#4 (5%): 2.0s , <1M
公開 測資點#5 (5%): 2.0s , <1K
公開 測資點#6 (5%): 2.0s , <1M
公開 測資點#7 (5%): 2.0s , <10M
公開 測資點#8 (5%): 2.0s , <1K
公開 測資點#9 (5%): 2.0s , <1K
公開 測資點#10 (5%): 2.0s , <1K
公開 測資點#11 (5%): 2.0s , <1K
公開 測資點#12 (5%): 2.0s , <10M
公開 測資點#13 (5%): 2.0s , <10M
公開 測資點#14 (5%): 2.0s , <10M
公開 測資點#15 (5%): 2.0s , <1M
公開 測資點#16 (5%): 2.0s , <1M
公開 測資點#17 (5%): 2.0s , <1M
公開 測資點#18 (5%): 2.0s , <1M
公開 測資點#19 (5%): 2.0s , <1K
Hint :

範例 2
柵欄長相如下圖,三張海報 (寬度為 2, 2, 1) 可以貼在高度為 $5$ 的高度。

Tags:
APCS 二分搜 貪心法
出處:
2022年1月APCS [管理者:
cthbst (吳宗達)
]


ID User Problem Subject Hit Post Date
28889
r1cky (木叢欉木叢)
h084
延伸題
487 2022-01-10 12:28
28873
r1cky (木叢欉木叢)
h084
解題提示
789 2022-01-09 21:21