【NOIP2018提高組D1T1】鋪設道路

題目描述

春春是一名道路工程師，負責鋪設一條長度為 n 的道路。

鋪設道路的主要工作是填平下陷的地表。整段道路可以看作是 n 塊首尾相連的區域，一開始，第 i 塊區域下陷的深度為 d[i] 。

春春每天可以選擇一段連續區間 [L,R] ，填充這段區間中的每塊區域，讓其下陷深度減少1。在選擇區間時，需要保證，區間内的每塊區域在填充前下陷深度均不為 0 。

春春希望你能幫他設計一種方案，可以在最短的時間内将整段道路的下陷深度都變為 0 。

資料範圍

• 1 ≤ n ≤ 1 0 5 1 \le n \le 10^5 1≤n≤105 0 ≤ d i ≤ 1 0 4 0 \le d_i \le 10^4 0≤di​≤104

題目分析

• 這道題非常的水(相似的題随處可找)
• 這裡的n非常小,完全可以支援 O ( n l o g n ) O(nlogn) O(nlogn)的算法,是以我們這裡先講一下此類算法

O ( n l o g n ) O(nlogn) O(nlogn)算法

• 我們知道,如果一個數在目前區間中是最小的話,那麼它肯定是最先變成0的(易證)
• 是以我們隻要找出每一個數它在哪個區間是最少的,很顯然,我們找出左邊和右邊第一個比它小的,整兩個數的中間部分就是所求區間
• 然後我們加上這一個數的貢獻,很顯然,隻有左右比它小的那兩個數耗光後它才會開始變成0,于是我們求出那兩個數的最大值,然後用目前這個數減去那個較大值,就是這個數的貢獻
• 最後把所有數的貢獻加起來即可
• 對于左邊和右邊第一個比它小的數,我們可以用線段樹等資料結構維護

O ( n ) O(n) O(n)算法

• 我們其實隻要推一波式子,就可以發現上面的方法可以簡化
• 簡單來說,就是下面這個公式
• ∑ i = 1 n m a x ( 0 , b [ i ] − b [ i − 1 ] ) \sum^{n}_{i=1}max(0,b[i]-b[i-1]) i=1∑n​max(0,b[i]−b[i−1])
• 其中 b [ 0 ] = 0 b[0]=0 b[0]=0,輸出此式子即可
• 至于細節就讓讀者自己思考(其實是自己懶 )