Description

在某條街上有著這么一行比較奇怪的建筑物：每棟建筑物都是一個(gè)矩形，而且他們是一
個(gè)挨著一個(gè)的。每棟建筑物都有它的寬度和高度。
Task：現(xiàn)在從左到右給出N 棟建筑物的信息。其中每棟建筑物的信息包括它的寬度和
高度。然后現(xiàn)在交給你一個(gè)刷墻任務(wù)：你每一次刷墻的形狀都必須是一個(gè)矩形。問(wèn)你最少需
要多少次才能把所有建筑物都刷完？

Input

輸入文件的第一行有一個(gè)整數(shù)N（1≤N≤106）。
接下來(lái)有N 行，每行有兩個(gè)整數(shù)Wi 和Hi(１≤Ｗi,Hi≤231?1，分別表示每棟建筑物
的寬度和高度。
注意，建筑物是從左到右一個(gè)緊挨著一個(gè)的。如果你還不明白這句話是什么意思，那么
就請(qǐng)看樣例的圖示吧！！！！

Output

輸出文件僅包含一個(gè)整數(shù)，表示你最少需要多少次才能完成這次刷墻任務(wù)。

Sample Input

5

1 2

1 3

2 2

2 5

1 4

Sample Output

4

Data Constraint

Hint

數(shù)據(jù)約定：
對(duì)于40%的數(shù)據(jù),1≤N≤5000
對(duì)于80%的數(shù)據(jù),1≤N≤250000
對(duì)于100%的數(shù)據(jù),1≤N≤106

Solution

• 觀察題目，可以發(fā)現(xiàn)一個(gè)神奇的性質(zhì)：

• 一棟建筑物的寬是毫無(wú)作用的！！！，與之可以直接視為 1 ！

• 為什么呢？因?yàn)樵谕粭澖ㄖ镏?#xff0c;高相等，原來(lái)怎么刷，就還是怎么刷。

• 那么問(wèn)題就轉(zhuǎn)化成簡(jiǎn)單的單調(diào)棧——粉刷柵欄問(wèn)題了！

• 維護(hù)一個(gè)遞增的單調(diào)棧，按高度進(jìn)行

• 當(dāng)這一高度比前一高度低時(shí)，就不斷彈棧，同時(shí)答案 +1 ，直到保持單調(diào)

• 如此不斷進(jìn)行，最后再加上棧中元素個(gè)數(shù)即可！

• 這樣時(shí)間復(fù)雜度為 O(N) ，輕松 AC ！

Code

#include<cstdio> using namespace std; int ans,top; int stack[1000001]; inline int read() {int data=0; char ch=0;while(ch<'0' || ch>'9') ch=getchar();while(ch>='0' && ch<='9') data=data*10+ch-'0',ch=getchar();return data; } int main() {int n=read();for(int i=1;i<=n;i++){int x=read(),y=read();while(y<stack[top]) top--,ans++;while(y==stack[top]) top--;stack[++top]=y;}printf("%d",ans+top);return 0; }

總結(jié)

以上是生活随笔為你收集整理的JZOJ 1220. Pla的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。