題目:https://zerojudge.tw/ShowProblem?problemid=q184
出處:APCS202501
解題想法:
長度為k的最小距離和,取中位數的點當成會議位置,
右半部使用兩個前綴和相減,左半部也使用兩個前綴和相減,再相減就可以獲得距離和,
演算法效率由O(n*k)降到O(n)。
使用minLeft[x]計算由左到右的dp[0]到dp[x]的最小值,minRight[x]計算由右到左的dp[n-k-1]到dp[0]的最小值,
最後使用minLeft與minRight計算左右兩邊非重疊區域相加的最小值,效率由O(n*n)降到O(n)。
以下程式TLE(執行時間過長)
參考程式碼