a174:
P-3-7. 正整數序列之最接近的區間和
內容
輸入一個正整數序列(A[1], A[2], …, A[n])，另外給了一個非負整數K，請計算哪些連續區段的和最接近K而不超過K，以及這樣的區間有幾個。
n不超過20萬，輸入數字與K皆不超過10億。
輸入說明
第一行是n與K，第二行n個整數是A[i]，同行數字以空白間隔。
輸出說明
第一行輸出最接近K但不超過K的和，第二行輸出這樣的區間有幾個。
範例輸入
#1
5 10 4 3 1 7 4
範例輸出
#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
公開 測資點#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
提示 ：
(4,3,1)與(1,7)兩個區間的和都是8
Sliding window，基本上是以兩個指標維護一段區間，然後逐步將這區間從前往後(從左往右)移動。維護兩個指標這一類的方法也有人稱為雙指標法，但也包含兩個指標從兩端往中間移動，就像我們曾在介紹過，在排好序的序列中尋找兩數相加之和的問題時，可以用兩個指標逐步移動來做，會比連續的二分搜還好。也有人稱為爬行法，維護一個逐步右移的區段很像是毛毛蟲的爬行，前方先往前，後方再跟上，不斷的重複這個亦步亦趨的方式
標籤:
出處:
AP325
[管理者：
]
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||