#46329: O(n) 解提示
ericshen19555@gmail.com
(暴力又被TLE)
學校
:
南光中學
編號 : 103121
來源 : [1.174.155.227]
最後登入時間 ：
2025-10-10 14:32:50
考慮某個位置 $i$ 的沙包，他要被搬去哪？如果 $a_i \gt k$ 則搬不動跳過；否則找右邊第一個 $a_j \ge a_i$ 的位置 $j$，因為若是 $a_j \lt a_i$ 則 $j$ 應該會較 $i$ 先被搬空。
而「找右邊第一個 $\ge$ 自己的」是單調棧裸題。