24h購物| | PChome| 登入
2011-06-01 22:18:12| 人氣711| 回應0 | 上一篇 | 下一篇

d825. 隔熱紙

推薦 0 收藏 0 轉貼0 訂閱站台

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;
}

台長: Morris
人氣(711) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: ZeroJudge |
此分類下一篇:d416. 投影最大值
此分類上一篇:d826. 暗門

是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入圖片中算式的結果(可能為0) 
(有*為必填)
TOP
詳全文