題目描述

小明的破舊圍欄又要噴涂油漆了。圍欄由N個木板構成，每個寬度都為1cm，但是高度各不相同。他給自己買了一個噴漆機器，噴涂頭恰好也是1cm寬。
小明的噴漆機器是直接噴射的，因此噴頭的每一個部位必須一直接觸到木板，否則尤其會污染他的農田。并且機器也必須時刻與地面平行。可以看出，小明每次必須在同一高度對木板噴涂，可以從左到右直到沒有圍欄可以噴漆。這樣，若干次噴漆之后，就可以將圍欄翻新啦！
由于機器的特殊性，小明希望噴涂的次數盡量的少。如下圖的圍欄情況，共有5塊木板，高度分別為2,3,4,1,2。第一次可以刷1~5，第二次刷1~3，第三次刷2~3，第四次刷3~3，第五次刷5~5。5次就可以刷完！（刷的順序可以隨意調整，也可以從上面開始刷）
?
小明想要知道至少需要刷多少次就可以把圍欄都刷完，請你幫忙計算一下！

輸入

第一行一個整數N，表示木板數量。
接下來N行，每行一個整數，表示每塊木板依次的高度。

輸出

翻新圍欄所需的最少噴漆次數。

樣例輸入

5 2 3 4 1 2

樣例輸出

5

提示

100%的數據1<=n<=100000，對于每個木板的高度0<=hi<=10000。

---

題目分析：又是一道被zx學長秒穿了的題目之一。。

一開始看到這個題目不知道該怎么維護，想用數據結構強行模擬這個過程，因為如果按照高度來的話，最多也只需要循環1e4次就夠了，但是實在沒想到合適的方法去維護每一次的過程

后來經過zx學長的提醒之后，意識到了這是一個貪心的題目，我們可以正著O(n)掃一遍整個序列，然后累加一下每兩個遞增子串之間的差值，答案就出來了

至于為什么答案會這么簡單，我們可以這樣想，每次刷當前柵欄的時候，我們肯定盡可能的多刷才能得到最優解，我們假設當前柵欄高度之下的柵欄已經處理完畢，那么我們就讓與當前柵欄將相連接的并且高度比當前柵欄還要高的柵欄的同一層一起刷上顏色，這樣就能保證答案最優了，也就是按照上述思路解出的答案了

代碼：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e5+100;int a[N];int main() { // freopen("input.txt","r",stdin);int n;scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",a+i);int ans=0;for(int i=1;i<=n;i++)if(a[i]>a[i-1])ans+=a[i]-a[i-1];printf("%d\n",ans);return 0; }

?

總結

以上是生活随笔為你收集整理的中石油训练赛 - 围栏翻新(思维+贪心+差分)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。