我們用一排 $n$ 個擋板建造水槽。擋板的寬度為 $1$，高度為正整數且均不相同，水槽前後是兩片長寬均為無限大的玻璃板 (見下圖例)。相鄰擋板的距離都是 $1$ ，故相鄰二擋板之間會形成底面積 $1$ 平方的水槽。
擋板由左而右依序由 $0$ 到 $(n – 1)$ 編號，第 $i$ 及 $(i + 1)$ 檔板中間的水槽稱為水槽 $i$。
現在將總量為 $w$ 立方公分的水緩緩注入水槽 $i$。注意水量可能溢出到別的水槽，但是由於所有擋板高度都不同，所以每當溢出時，只會先從一個方向溢出。請計算將總量為 $w$ 立方公分的水緩緩注入水槽 $i$ 後，所有水槽的水深。
本題最左的擋板與最右的擋板是所有擋板中最高的兩個，並且保證欲注入的水不會溢出到左右邊界之外；另外，所有水槽的最後水深一定都是整數。
以下圖為例，於水槽 $2$ 注入 $17$ 立方公分的水後，各水槽的水深依序為 $[5, 5, 5, 1, 1, 0]$。
第一行有三個正整數 $n$、$i$ 和 $w$ ，分別代表擋板數、注水水槽編號，及水量。
第二行有 $n$ 個以空白間隔的正整數，代表由左到右擋板的高度。
- $3 \leq n \leq 10^5$
- $0 \leq i \leq n – 2$
- $1 \leq w \leq 10^{12}$
- 每個擋板高度為正整數且不超過109。
請注意注水量可能超過一個32-bit整數的範圍。。
輸出爲一行，共 $(n – 1)$ 個整數，依序代表各個水槽水深，數字之間以一個空白間隔。
7 2 17 999 3 2 5 1 6 998
5 5 5 1 1 0
8 3 27 9 7 5 3 4 6 8 10
0 6 6 6 6 3 0
公開 測資點#0 (20%): 1.0s , <1M
公開 測資點#1 (20%): 1.0s , <1M
公開 測資點#2 (20%): 1.0s , <1M
公開 測資點#3 (20%): 1.0s , <1M
公開 測資點#4 (20%): 1.0s , <1M
我們維護一個水槽高度尚未被決定的區間 [left,right) ，區間以外的水槽高度都已經確定。遞迴函數 rec(left, right, water, input)計算水量 water 從編號 input 進入後區間的各高度。
如果區間只剩一個水槽，該水槽高度=水量，結束；否則，在區間中找出最高的隔板，假設此隔板高度為H。區間被此隔板分成左右兩邊，考慮下面三種情形:
water >=(right-left)*H，水量足以讓兩邊都至少 H，區間內所有水槽高度皆是相同的平均值，結束。- 水量不足以越過輸入這一邊，那麼，另外一邊一定不會有水，縮小區間遞迴呼叫。
- 水量會越過輸入這一邊，那麼，輸入這一邊的水槽高度一定都是 H，把水量扣掉後遞迴呼叫另外一邊。
為了要找出區間內的最高隔板，我們可以一開始把所有隔板的依照高度從高到低排列，每次要找某區間最高隔板時，我們檢視目前最高的隔板，如果在我們要的區間，那就找到了；如果不在我們要的區間，這個隔板以後也不會用到(想想為何)，可以直接丟掉。因此，只要一開始把隔板排序後依序往後找就可以了，不需要特殊的資料結構，但是要把隔板的高度與位置一起存，所以需要一個兩個欄位資料的排序。
| ID | User | Problem | Subject | Hit | Post Date |
沒有發現任何「解題報告」 |
|||||