相信各位看到題目後,應該可以畫出這樣一張圖:
(k = 3, n = 20)
A + B + C + D
A + B + C + D + E
A + B + C + D + E + F
A + B + C + D + E + F + G
B + C + D + E + F + G + H
C + D + E + F + G + H + I
D + E + F + G + H + I + J
E + F + G + H + I + J + K
F + G + H + I + J + K + L
G + H + I + J + K + L + M
H + I + J + K + L + M + N
I + J + K + L + M + N + O
J + K + L + M + N + O + P
K + L + M + N + O + P + Q
L + M + N + O + P + Q
M + N + O + P + Q
N + O + P + Q
(上圖每一行的總和就是一個輸入的數字,不難理解吧?)
並且覺得:我應該可以把它消掉求解吧?
然而否,事實上我們只需要用搜尋的就可以了
不妨試試看從第1行開始看
第零行結尾是E,所以我們從開頭是F的開始繼續。開頭是F的這行結尾是L,開頭是M的結尾恰好就是最後了,因此只要把他們全部加起來就是解答了。
雖然可以用公式解到底是哪行,但是反正這題k到4000,N到200000,複雜度就是 O(K * N / K) (N/K是把每個項目總合加起來的時間,K是把k從0帶到K+1),所以看起來搜索就可以過了,就不用花心思算數學了(會掉頭髮)
假代碼如下
i 從零帶到 K+1 (含)
總和 = 0
x = i
若 行代號 < N - K - 1 重複執行:
總和 = 總和 + 第x行
x += 2 * K + 1 // 每一固定行的寬度
若 (x == N-1) 或 ((N - K - 1) - x >= 0):
總和 += 第x行
印出 總和
結束程序
// 發生錯誤,程序失敗