2011-06-01 22:18:12Morris
d825. 隔熱紙
http://zerojudge.tw/ShowProblem?problemid=d825
內容 ：
喵嗚建設公司最近由北到南蓋了一整排共n棟的大樓，且每棟大樓是緊緊貼在一起的
而喵嗚建設公司希望能夠帶給住戶舒適的住宅環境，因此決定在東面窗上貼滿隔熱紙
然而預算有限，不能有任何隔熱紙被浪費，又切割隔熱紙是一向充滿麻煩的工程
你可以幫喵嗚建設公司算出至少要幾張矩形的隔熱紙才能貼滿整排大樓的東側嗎？
輸入說明
：
第一行有一個正整數 n(n<=100000)，代表有幾棟大樓
接下來n行每行有兩個正整數(<=1,000,000,000)，依序代表每棟大樓的寬度及高度
輸出說明
：
輸出最少所需要的隔熱紙數
範例輸入 ：
5 1 2 1 3 2 2 2 5 1 4
範例輸出 ：
4
提示
：
不能浪費隔熱紙即隔熱紙間不能重疊，且隔熱紙需完全緊貼在大樓東面上
出處
：
(管理：shik)
/**********************************************************************************/
/* Problem: d825 "隔熱紙" from */
/* Language: C */
/* Result: AC (20ms, 649KB) on ZeroJudge */
/* Author: morris1028 at 2011-06-01 19:01:25 */
/**********************************************************************************/
#include<stdio.h>
main() {
int n, x, t = 0, A = 0, stack[100000] = {};
scanf("%d", &n);
while(n--) {
scanf("%d %d", &x, &x);
while(x < stack[t]) A++, t--;
if(x != stack[t]) stack[++t] = x;
}
printf("%d\n", A + t);
return 0;
}
上一篇：d826. 暗門
下一篇：d416. 投影最大值