先假定m = s + 1然後計算題目要求的總和值acc

m = s + 1時，acc = (-1) * p[s] +   0  * p[s + 1] +  1 * p[s + 2] + ...


m = s + 2時，acc = (-2) * p[s] + (-1) * p[s + 1] +  0 * p[s + 2] + ...

可以推出acc在m = s + 2時比m = s + 1少Σp[i], i∈[s, t]

這邊先設sum = Σp[i], i∈[s, t]

如果m = s + 1時算出來的acc <= 0，那切點就是s + 1，因為再減下去絕對值只會更大

而如果acc > 0，那就要計算是acc、acc - sum * n、acc - sum * (n + 1)哪個的絕對值最小

可以得

n = acc / sum

m = s + 1 + n

接著寫幾個if就出來了

別忘了判斷m要在[s+1, t-1]之間

先假定m = s + 1然後計算題目要求的總和值acc

m = s + 1時，acc = (-1) * p[s] +   0  * p[s + 1] +  1 * p[s + 2] + ...


m = s + 2時，acc = (-2) * p[s] + (-1) * p[s + 1] +  0 * p[s + 2] + ...

可以推出acc在m = s + 2時比m = s + 1少Σp[i], i∈[s, t]

這邊先設sum = Σp[i], i∈[s, t]

如果m = s + 1時算出來的acc <= 0，那切點就是s + 1，因為再減下去絕對值只會更大

而如果acc > 0，那就要計算是acc、acc - sum * n、acc - sum * (n + 1)哪個的絕對值最小

可以得

n = acc / sum

m = s + 1 + n

接著寫幾個if就出來了

別忘了判斷m要在[s+1, t-1]之間

 

Σp[i], i∈[s, t]可以用前綴和求出