[心得] 1到N求連續整數和為Y在O(N)解

[bleed1979 (十三)]

剛才的文章被刪掉了，還是稍微講一下好了。

1到N連續整數和為Y

0.left = 1, Z = 0

1.Z + left + (left + 1) + (left + 2) ..... + X  = Z1 直到 >= Y

2.如果等於 goto end.

3.如果大於 Z1 - left - (left + 1) 直到小於等於Y

4.如果等於 goto end.

5.如果小於 goto 1. 把Z替換成小於的Z

end.

就是一直右邊增左邊減的夾擠，應該是這樣吧，不知有沒有洞，有錯請指正討論。


Bleed

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 114.32.177.97
推 loveme00835:簡單說就是建一個 partial sum 的表格, 再用兩個索引
→ loveme00835:一左一右相減
推 yuscvscv:queue?
→ bleed1979:http://codepad.org/FNmmSom2  code大概長這樣(待修)
推 loveme00835:我也試作了一個 XD http://nopaste.csie.org/f687d
推 holymars:連加法不就梯形公式@@..既然要求整數解　用因數分解
→ holymars:就可以了吧　感覺不需要到0(N) ?
推 ledia:梯形公式有兩個參數喔
推 elfkiller:因數分解複雜度沒有比較低吧
推 loveme00835:原題目是要陣列裡的元素吧=  =
推 loveme00835:陣列B裡找區間[i:j]裡元素和=Y