d031: 例題 P-3-7. 正整數序列之最接近的區間和
Tags : Binary Search prefix sum two pointer
Accepted rate : 177人/184人 ( 96% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-03-28 15:02

Content

輸入一個正整數序列 $(A[1], A[2], ..., A[n])$ ,另外給了一個非負整數 $K$ ,請計算哪些連續區段的和最接近 $K$ 而不超過 $K$,以及這樣的區間有幾個。

$n$ 不超過 20 萬,輸入數字與 $K$ 皆不超過 10 億。

Input

第一行是 $n$ 與 $K$,

第二行 $n$ 個整數是 $A[i]$,同行數字以空白間隔。

Output

第一行輸出最接近 $K$ 但不超過 $K$ 的和,

第二行輸出這樣的區間有幾個。

Sample Input #1
5 10
4 3 1 7 4
Sample Output #1
8
2
測資資訊:
記憶體限制: 64 MB
不公開 測資點#0 (20%): 1.0s , <10M
不公開 測資點#1 (20%): 1.0s , <10M
不公開 測資點#2 (20%): 1.0s , <10M
不公開 測資點#3 (20%): 1.0s , <10M
不公開 測資點#4 (20%): 1.0s , <10M
Hint :

感謝 yes51851823 已更正範例輸出格式。

 

$nevikw39$

Tags:
Binary Search prefix sum two pointer
出處:
AP325 [管理者:
TCIRC ($\mathbb{TCFSH}\ \mathtt{Comp.}\ \&\ \mathsf{Info.}\ \mathit{Club}$)
]


ID User Problem Subject Hit Post Date
69
yes51851823@... (wseds)
d031
別被範例搞混了
615 2021-04-14 14:53