柊四千的倉庫

筆者這次也參與了全國賽的驗題，這邊放一份另一位驗題者與筆者提供的詳解。題本的連結在 這裡 ，pC / pE / pH / pI 的時間限制分別為 2.5s / 2.5s / 2.0s / 0.1s，其餘題目皆為 1.0s。另，讀者也能在 這裡 找到與下文基本相同的內容。 A. 髮廊服務優化問題 (barbershop) 有 $n$ 個人一起來店，第 $i$ 個人的服務時間為 $t_i$。每個客人等待時間是前面人 $+$ 自己服務時間總和，求等待時間總和的最小值。例如：三個人服務時間為 $2,1,3$，若服務順序為 $1,2,3$ 則等待時間總和為 $2 + (2+1) + (2+1+3) = 11$。 等價題序：給一個陣列 $\mathbf{t} := \{t_i\}_{i=1}^n$，將 $\mathbf{t}$ 重新排列使得 $nt_1 + (n-1)t_2 + (n-2)t_3 + \ldots + t_n$ 最小。由上式不難得知，順序越前面被乘的係數就越大，所以可以貪心地將數字從小排到大。複雜度 $O(n \log n)$。 B. 校園公車 (bus) 給定由 $n$ 條線段組成的折線 $\mathbf{P} := \left\{ \overline{P_i P_{i+1}} \right\}_{i=1}^n$ 與一點 $O$，問 $O$ 到 $\mathbf{P}$ 的最短距離。 先考慮這個問題：給定一線段 $\overline{PQ}$ 與一點 $O$，求 $O$ 到 $\overline{PQ}$ 的距離。首先我們作 $O$ 到 $\overline{PQ}$ 的垂足 $H$，並試著計算 $\overline{OH}$。注意 $\overline{OH}$ 其實就是 $\Delta OPQ$ 以 $\overline{PQ}$ 為底時的高，所以可以用下面的方法計算： Length_OH(O: Point, PQ: Segment): A ← ΔOPQ return 2A/|PQ| $\Delta OPQ$ 可以用 Shoelace formula 計算。 但事情沒有這麼簡單。$O$ 到 $\overline{PQ}$ 的距離並不總是 $\overline{OH}$：當 $\angle OPQ