1628: [Usaco2007 Demo]City skyline
Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 256 Solved: 210
[Submit][Status]
Description
sets. They can see the skyline of the distant city. Bessie wonders
how many buildings the city has. Write a program that assists the
cows in calculating the minimum number of buildings in the city,
given a profile of its skyline.
The city in profile is quite dull architecturally, featuring only
box-shaped buildings. The skyline of a city on the horizon is
somewhere between 1 and W units wide (1 <= W <= 1,000,000) and
described using N (1 <= N <= 50,000) successive x and y coordinates
(1 <= x <= W, 0 <= y <= 500,000), defining at what point the skyline
changes to a certain height.
An example skyline could be:
..........................
.....XX.........XXX.......
.XXX.XX.......XXXXXXX.....
XXXXXXXXXX....XXXXXXXXXXXX
and would be encoded as (1,1), (2,2), (5,1), (6,3), (8,1), (11,0), (15,2),
(17,3), (20,2), (22,1).
给我们一个由一些矩形构造出来的图，我们需要找到最少矩形的块数来覆盖它
但是这个输入比较奇怪,针对上图,解释如下:
1.1代表在第一列,有高度为1的矩形,矩形由"X"组成.这个矩形有多宽呢,这里并没有告诉你
2.2代表在第二列,有高度为2的矩形,这就间接告诉了你,前面那个矩形有多宽,宽度即2-1
5.1代表在第五列,有高度为1的矩形,这就间接告诉了你,前面那个矩形有多宽,宽度即5-2
This skyline requires a minimum of 6 buildings to form; below is
one possible set of six buildings whose could create the skyline
above:
.......................... ..........................
.....22.........333....... .....XX.........XXX.......
.111.22.......XX333XX..... .XXX.XX.......5555555.....
X111X22XXX....XX333XXXXXXX 4444444444....5555555XXXXX
..........................
.....XX.........XXX.......
.XXX.XX.......XXXXXXX.....
XXXXXXXXXX....666666666666
Input
* Lines 2..N+1: Two space separated integers, the x and y coordinate
of a point where the skyline changes. The x coordinates are
presented in strictly increasing order, and the first x
coordinate will always be 1.
Output
skyline.
Sample Input
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
HINT
Source
题解：
cf原题？完全忘了。。。
比较巧妙。首先应该知道 ans<=n，然后考虑ans<n什么情况下会出现？
显然应该是 有两块相同高度的积木，并且这两块积木中间没有比它们低的积木！
那就是单调栈了。
发现OI真是有时候不是看你会不会什么算法，而是你能不能想到某个算法。
代码：
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<string>
#define inf 1000000000
#define maxn 50000+100
#define maxm 500+100
#define eps 1e-10
#define ll long long
#define pa pair<int,int>
#define for0(i,n) for(int i=0;i<=(n);i++)
#define for1(i,n) for(int i=1;i<=(n);i++)
#define for2(i,x,y) for(int i=(x);i<=(y);i++)
#define for3(i,x,y) for(int i=(x);i>=(y);i--)
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=*x+ch-'';ch=getchar();}
return x*f;
}
int a[maxn],sta[maxn],n,m;
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
n=read();m=read();
for1(i,n)a[i]=read(),a[i]=read();
int top=,ans=n;
for1(i,n)
{
while(a[sta[top]]>a[i])top--;
if(a[sta[top]]==a[i])ans--;else sta[++top]=i;
}
printf("%d\n",ans);
return ;
}