BZOJ_1628_[Usaco2007_Demo]_City_skyline_(单调栈)

描述



http://www.lydsy.com/JudgeOnline/problem.php?id=1628

给出\(n\)个距形的影子,问最少是多少个建筑的?(建筑的影子可以重叠).

分析



用单调栈维护一下.

栈内是可能"延续"到当前位置的之前的影子.那么显然比当前位置高的不可能.如果有和当前位置等高的影子,就延续过来,就可以少一个建筑,否则,就向栈里加入当前位置高度的影子.

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3
 4 const int maxn=50000+5;
 5 int n,m,top,ans;
 6 int a[maxn],s[maxn];
 7 int main(){
 8     scanf("%d%d",&n,&m); ans=n;
 9     for(int i=1;i<=n;i++) scanf("%d",&a[i]), scanf("%d",&a[i]);
10     for(int i=1;i<=n;i++){
11         while(s[top]>a[i]) top--;
12         if(s[top]==a[i]) ans--;
13         else s[++top]=a[i];
14     }
15     printf("%d\n",ans);
16     return 0;
17 }

1628: [Usaco2007 Demo]City skyline

Time Limit: 5 Sec  Memory Limit: 64 MB
Submit: 432  Solved: 344
[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

Silver

时间: 07-07

BZOJ_1628_[Usaco2007_Demo]_City_skyline_(单调栈)的相关文章

(单调栈)poj-2559 Largest Rectangle in a Histogram

A histogram is a polygon composed of a sequence of rectangles aligned at a common base line. The rectangles have equal widths but may have different heights. For example, the figure on the left shows the histogram that consists of rectangles with the

【单调栈】hdu1506 Largest Rectangle in a Histogram

单调栈的介绍及一些基本性质 http://blog.csdn.net/liujian20150808/article/details/50752861 依次把矩形塞进单调栈,保持其单增,矩形中的元素是一个三元组,存储其位置,高度,以及以其为高度的情况下,大矩形的左边界最多扩展到哪里. 每次将新的元素塞进栈的时候,其左边界就是其左侧第一个小于它的矩形的位置+1. 然后,每个矩形出栈的时候,记录其右边界为当前往栈里面塞的矩形的位置-1,然后更新答案即可. 注意最后把所有的矩形出栈,更新答案. #in

BZOJ 3238 AHOI 2013 差异 后缀数组+单调栈

题目大意: 思路:一看各种后缀那就是后缀数组没跑了. 求出sa,height之后就可以乱搞了.对于height数组中的一个值,height[i]来说,这个值能够作为lcp值的作用域只在左边第一个比他小的位置到右边第一个比他小的位置.这个东西很明显可以倍增RMQ+二分/单调栈. 之后就是数学题了 Σlen[Ti] + len[Tj] = (len + 1) * len * (len - 1),之后吧所有求出来的Σ2 * lcp(Ti,Tj)减掉就是答案. 记得答案开long long CODE:

51nod 1215 数组的宽度&amp;poj 2796 Feel Good(单调栈)

单调栈求每个数在哪些区间是最值的经典操作. 把数一个一个丢进单调栈,弹出的时候[st[top-1]+1,i-1]这段区间就是弹出的数为最值的区间. poj2796 弹出的时候更新答案即可 #include<iostream> #include<cstdlib> #include<cstring> #include<cstdio> #include<algorithm> #include<queue> #include<cmath

[poj3250]单调栈 Bad Hair Day

解题关键:将每头牛看到的牛头数总和转化为每头牛被看到的次数,然后用单调栈求解,其实做这道题的目的只是熟悉下单调栈 此题为递减栈 1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<cstdlib> 5 #include<stack> 6 #include<iostream> 7 using namespace std; 8 typedef lo

HDU 5033---Building(单调栈)

题目链接 Problem Description Once upon a time Matt went to a small town. The town was so small and narrow that he can regard the town as a pivot. There were some skyscrapers in the town, each located at position xi with its height hi. All skyscrapers loc

POJ 3415 Common Substrings(后缀数组+单调栈)

[题目链接] http://poj.org/problem?id=3415 [题目大意] 求出两个字符串长度大于k的公共子串的数目. [题解] 首先,很容易想到O(n2)的算法,将A串和B串加拼接符相连, 做一遍后缀数组,把分别属于A和B的所有后缀匹配,LCP-k+1就是对答案的贡献, 但是在这个基础上该如何优化呢. 我们可以发现按照sa的顺序下来,每个后缀和前面的串的LCP就是区间LCP的最小值, 那么我们维护一个单调栈,将所有单调递减的LCP值合并, 保存数量和长度,对每个属于B串的后缀更新

poj2796 维护区间栈//单调栈

http://poj.org/problem?id=2796 题意:给你一段区间,需要你求出(在这段区间之类的最小值*这段区间所有元素之和)的最大值...... 例如: 6 3 1 6 4 5 2 以4为最小值,向左右延伸,6 4 5  值为60....... 思路:解决完为这道题目,我才真正明白了单调栈的原理,它就是以某一个值为最小(最大)值,向这个值的两侧延伸,遇到大于它(小于它)的值,就将它延伸的范围扩大,当然,一般来说,要这样做的算法复杂度为o(n^2),但是借助栈这个玩意,维护其单调增

hdu 5875(单调栈)

Function Time Limit: 7000/3500 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)Total Submission(s): 1866    Accepted Submission(s): 674 Problem Description The shorter, the simpler. With this problem, you should be convinced of this tr