PKU2140-Herd Sums

題目：http://poj.org/problem?id=2140
給一正整數n(最多一千萬)
問有多少種i,j (1<=i<=j<=n)可以達成sigma(k=i...j) k = n
例如15可以是15, 7+8, 4+5+6, 1+2+3+4+5這四種方法

對了，原來Farmer John大學主修數學(炸)


程式碼：http://codepad.org/qMX6HCQk

我相當喜歡這道題目，名題百選也有收錄這題，適合鍛鍊思考
我們選擇枚舉末尾j、設定一開始i=1
並且維護i...j這段的總和sum，是為可能是答案的段落
每次檢查目前i...j是不是太肥了，每次超過n，就讓i前進一格
順利讓i...j的總和<=n，再來檢查如果剛好是n就讓答案數增加
這就是整個算法

因為如果i...j總和已經太大，那麼i...j+1也不可能是答案，可以放棄考慮i的可能性

這很像毛毛蟲一樣先讓頭前進，再用身體的力道拖著尾巴前進
也很像陣列實作的數據結構Queue
是很有意思的應用