先假定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]可以用前綴和求出