看板 TL
作者 標題 [筆記] [心得] 1到N求連續整數和為Y在O(N)解
時間 2013年01月27日 Sun. PM 06:45:46
看板 C_and_CPP
作者 標題 [心得] 1到N求連續整數和為Y在O(N)解
時間 Sun Mar 14 20:49:54 2010
剛才的文章被刪掉了，還是稍微講一下好了。
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
推 :簡單說就是建一個 partial sum 的表格, 再用兩個索引1F 03/14 20:55
→ :一左一右相減
→ :一左一右相減
推 :queue?3F 03/14 21:01
推 :連加法不就梯形公式@@..既然要求整數解 用因數分解6F 03/14 22:43
→ :就可以了吧 感覺不需要到0(N) ?
→ :就可以了吧 感覺不需要到0(N) ?
推 :梯形公式有兩個參數喔8F 03/14 23:25
推 :因數分解複雜度沒有比較低吧9F 03/14 23:28
推 :原題目是要陣列裡的元素吧= =10F 03/15 00:45
推 :陣列B裡找區間[i:j]裡元素和=Y
推 :陣列B裡找區間[i:j]裡元素和=Y
--
Shaken, Not Stirred.
--
※ 作者: TL 時間: 2013-01-27 18:45:46
※ 看板: TL 文章推薦值: 0 目前人氣: 0 累積人氣: 29
回列表(←)
分享