› 看板 C_and_CPP 關於我們 聯絡資訊
作者bleed1979 (十三)
看板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
推 loveme00835:簡單說就是建一個 partial sum 的表格, 再用兩個索引 03/14 20:55
→ loveme00835:一左一右相減 03/14 20:56
推 yuscvscv:queue? 03/14 21:01
→ bleed1979:http://codepad.org/FNmmSom2 code大概長這樣(待修) 03/14 21:31
推 loveme00835:我也試作了一個 XD http://nopaste.csie.org/f687d 03/14 21:50
推 holymars:連加法不就梯形公式@@..既然要求整數解　用因數分解 03/14 22:43
→ holymars:就可以了吧　感覺不需要到0(N) ? 03/14 22:44
推 ledia:梯形公式有兩個參數喔 03/14 23:25
推 elfkiller:因數分解複雜度沒有比較低吧 03/14 23:28
推 loveme00835:原題目是要陣列裡的元素吧= = 03/15 00:45
推 loveme00835:陣列B裡找區間[i:j]裡元素和=Y 03/15 00:51
推 yuscvscv:那就只能線性queue了 03/15 02:53
推 holymars:從原po貼的code來看　不像是陣列裡的元素和 03/15 13:40
→ holymars:題目都寫「連續整數」了...另外因數分解複雜度才O(N^1/2) 03/15 13:41
推 holymars:Y乘2作因數分解　隨便找一組a*b=Y*2 只要ab不是均偶數 03/15 13:43
→ holymars:就能從ab找一組連續整數和出來啊 03/15 13:43
→ holymars:嗯..應該不完全是因數分解(因為不用分完)　反正是找ab 03/15 13:44
推 holymars:欸我看錯N和Y了　因數分解的複雜度是O(Y^(1/2)) 03/15 13:50
推 DJWS:名題精選百則/冼鏡光 問題2.16 連續整數的固定和 03/15 14:15
推 loveme00835:bleed1979 不是原po阿~~> < 03/15 14:24
推 loveme00835:陣列內容只要換掉, 一樣可解連續整數和 03/15 14:29