這題被小乃瞬秒XD 不過其實還頗有趣的 .
Description:
定義一個數列S的Mean序列M:
Mi = (Si + S(i+1))/2
例如 序列1, 1, 3, 5, 15的M為: 1, 2, 4, 10
給你一個有n項的序列M,請問有多少S使得
1. S的Mean序列為M
2. S1 <= S2 <= S3 <= ... <= S(n+1)
n<= 5,000,000
Solution:
M2-M1 = (S3-S1)/2
依此,可以把奇數項和偶數項分開討論,例如範例就變成
(a), (b), (a+2), (b+4), (a+14)
再由條件2.
(a)<= (b)<= (a+2)<= (b+4)<= (a+14)
解不等式 加上a+b = 2(M1)驗證
總複雜度O(n)
沒有留言:
張貼留言