透過前綴和可以先算出

a0

a0+a1

a0+a1+a2

我們稱這個數列為prefixsum[n]

這時候會疑惑說題目要求的還必須乘上距離，所以我們要把前綴和再做一次，就會變成

a0

2a0+a1

3a0+2a1+a2

我們稱這個數列為sum[n]

就是題目所求的，然後因為有兩邊需要計算，所以上面的方式我們要做兩次，從數列的兩邊分別計算

接著就可以依照吳邦一教授的範例，訪寫一個遞迴函式，傳入左界跟右界還有已經切的次數

當左界和右界的差小於2時，或切的次數已經抵達上限則回傳

然後窮舉切點，這時候就會遇到以下情況：

左界的位置為a0、右界的位置為an-1

->直接分別套用兩邊的所做的兩次前綴和結果(即rsum[] & lsum[])

左界的位置大於a0、右界的位置小於an-1

->以下以左界的情況為範例說明：

數列為a0......aL......aR......an-1
設窮舉的切點為ai

這時我們要算的就會變成lsum[i-1] - lsum[L-1] - (i-L)*lprefixsum[L-1]

舉實例說明:

數列為a0 a1 a2 a3 a4

當今天aL為a2 ai為a3時

按照題目所求的答案應為a2

而lsum[3-1] = 3a0+2a1+a0

   lsum[2-1] = 2a0+a1

   這時候我們差一個修正項，透過簡單的數學運算推理就可以知道修正項為aL到(ai前)的個數(注意不包含ai，因為他是切點)乘上左界前一個元素的前綴和

   即(i-L)*lprefixsum[L-1] = (3-2)*(a0+a1) = a0+a1

右邊的情況依此類推，順帶一提從右邊數來的index = N-i-1

然後在窮舉切點的過程中要記錄兩邊的最小差值，最後找到適合切點，回傳的撰寫方式與教授的範例類似

切記要在找到最適合切點的時候將次數+1

以上是我的解題思維，如果有任何錯誤請海涵，有任何疑問也可以向我發送訊息，謝謝您的閱讀

感謝解釋

透過前綴和可以先算出

a0

a0+a1

a0+a1+a2

我們稱這個數列為prefixsum[n]

這時候會疑惑說題目要求的還必須乘上距離，所以我們要把前綴和再做一次，就會變成

a0

2a0+a1

3a0+2a1+a2

我們稱這個數列為sum[n]

就是題目所求的，然後因為有兩邊需要計算，所以上面的方式我們要做兩次，從數列的兩邊分別計算

接著就可以依照吳邦一教授的範例，訪寫一個遞迴函式，傳入左界跟右界還有已經切的次數

當左界和右界的差小於2時，或切的次數已經抵達上限則回傳

然後窮舉切點，這時候就會遇到以下情況：

左界的位置為a0、右界的位置為an-1

->直接分別套用兩邊的所做的兩次前綴和結果(即rsum[] & lsum[])

左界的位置大於a0、右界的位置小於an-1

->以下以左界的情況為範例說明：

數列為a0......aL......aR......an-1
設窮舉的切點為ai

這時我們要算的就會變成lsum[i-1] - lsum[L-1] - (i-L)*lprefixsum[L-1]

舉實例說明:

數列為a0 a1 a2 a3 a4

當今天aL為a2 ai為a3時

按照題目所求的答案應為a2

而lsum[3-1] = 3a0+2a1+a0

   lsum[2-1] = 2a0+a1

   這時候我們差一個修正項，透過簡單的數學運算推理就可以知道修正項為aL到(ai前)的個數(注意不包含ai，因為他是切點)乘上左界前一個元素的前綴和

   即(i-L)*lprefixsum[L-1] = (3-2)*(a0+a1) = a0+a1

 

右邊的情況依此類推，順帶一提從右邊數來的index = N-i-1

然後在窮舉切點的過程中要記錄兩邊的最小差值，最後找到適合切點，回傳的撰寫方式與教授的範例類似

切記要在找到最適合切點的時候將次數+1

 

以上是我的解題思維，如果有任何錯誤請海涵，有任何疑問也可以向我發送訊息，謝謝您的閱讀

謝謝題解~