d023: 習題 Q-2-14. 水槽 (108 高中全國賽) (@@)
Tags :
Accepted rate : 3人/4人 ( 75% ) [非即時]
評分方式:
Tolerant

最近更新 : 2021-02-08 11:30

Content

我們用一排 $n$ 個擋板建造水槽。擋板的寬度為 $1$,高度為正整數且均不相同,水槽前後是兩片長寬均為無限大的玻璃板 (見下圖例)。相鄰擋板的距離都是 $1$,故相鄰二擋板之間會形成底面積 $1$ 平方的水槽。

擋板由左而右依序由 $0$ 到 $n – 1$ 編號,第 $i$ 及 $i + 1$ 檔板中間的水槽稱為水槽 $i$。現在將總量為 $w$ 立方公分的水緩緩注入水槽 $i$。注意水量可能溢出到別的水槽,但是由於所有擋板高度都不同,所以每當溢出時,只會先從一個方向溢出。請計算將總量為 $w$ 立方公分的水緩緩注入水槽 $i$ 後,所有水槽的水深。本題最左的擋板與最右的擋板是所有擋板中最高的兩個,並且保證欲注入的水不會溢出到左右邊界之外;另外,所有水槽的最後水深一定都是整數。以下圖為例,於水槽 $2$ 注入 $17$ 立方公分的水後,各水槽的水深依序為 $5, 5, 5, 1, 1, 0$。

 

 

Input

第一行有三個正整數 $n (3 \leq n \leq10^5)$、$i (0 \leq i \leq n–2)$和$w (1 \leq w \leq 10^{12})$,分別代表擋板數、注水水槽編號及水量。第二行有 $n$ 個以空白間隔的正整數,代表由左到右擋板的高度,每個擋板高度為正整數且不超過 $10^9$)。請注意注水量可能超過一個 32-bit 整數的範圍。

Output

輸出爲一行,共 $n – 1$ 個整數,依序代表各個水槽水深,數字之間以一個空白間隔。

Sample Input
8 3 27
9 7 5 3 4 6 8 10
Sample Output
0 6 6 6 6 3 0
測資資訊:
記憶體限制: 64 MB
公開 測資點#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
Hint :
Tags:
出處:
AP325 [管理者:
TCIRC ($\mathbb{TCFSH}\mathtt{Computer}\mathsf{Information}\mathit{Club}$)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」