h084. 4. 牆上海報
標籤 : APCS 二分搜 貪心法
通過比率 : 937人/1075人 ( 87% ) [非即時]
評分方式:
Tolerant

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

內容

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

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

輸入說明

第一行有兩個正整數 $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%): 無額外限制
輸出說明

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

範例輸入 #1
5 1
6 3 7 5 1
3
範例輸出 #1
3
範例輸入 #2
10 3
5 3 7 5 1 7 5 3 8 4
2 2 1
範例輸出 #2
5
測資資訊:
記憶體限制: 512 MB
提示 :

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

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

本題狀況 本題討論 排行

編號 身分 題目 主題 人氣 發表日期
44325 janray200804 ... (jan ray) h084
錯但有趣的答案
49 2024-11-25 18:37
41181 glps1004@gma ... (Ian) h084
APCS202201
195 2024-07-09 15:11
40635 toseanlin@gm ... (Dr. SeanXD) h084
C++詳解
307 2024-06-03 10:15
40456 qerpzzea@gma ... (賽希爾 cecill(陳宥穎)) h084
204 2024-05-21 21:07
36818 fire5386 (becaidorz) h084
簡易題解
550 2023-08-10 14:21