首页 > 其他 > 详细

[Usaco2007 Demo][BZOJ1628] City skyline

时间:2015-07-22 18:39:29      阅读:242      评论:0      收藏:0      [点我收藏+]

1628: [Usaco2007 Demo]City skyline

Time Limit: 5 Sec  Memory Limit: 64 MB
Submit: 320  Solved: 260
[Submit][Status][Discuss]

Description

技术分享

Input

第一行给出N,W
第二行到第N+1行:每行给出二个整数x,y,输入的x严格递增,并且第一个x总是1

Output

输出一个整数,表示城市中最少包含的建筑物数量

Sample Input

10 26
1 1
2 2
5 1
6 3
8 1
11 0
15 2
17 3
20 2
22 1

INPUT DETAILS:

The case mentioned above

Sample Output

6

HINT

 

Source

 
单调栈
首先至多有n个建筑物,如果有两个高度相等的楼且这两栋楼之间没有比这些楼更矮的楼,那么建筑物数量就可-1。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<set>
using namespace std;
int n,x,w,h[50005],ans,top,stack[50005];
int main()
{
    scanf("%d%d",&n,&w);
    ans=n; 
    for (int i=1;i<=n;i++) scanf("%d%d",&x,&h[i]);
    for (int i=1;i<=n;i++) 
    {
        while (h[i]<stack[top]) top--;
        if (h[i]==stack[top]) ans--;
            else stack[++top]=h[i];
    }
    printf("%d",ans);
    return 0;
}

 

[Usaco2007 Demo][BZOJ1628] City skyline

原文:http://www.cnblogs.com/ws-fqk/p/4668063.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!