「BZOJ1683」[Usaco2005 Nov] City skyline 城市地平线

2014年7月28日3,4460

Description

Input

第1行：2个用空格隔开的整数N和W.

第2到N+1行：每行包括2个用空格隔开的整数x,y，其意义如题中所述．输入中的x严格递增，并且第一个z总是x．

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

题解

同1628

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int n,m,ans,top;
int h[50005],st[50005];
int main()
{
	n=read();m=read();
	for(int i=1;i<=n;i++)
	    h[i]=read(),h[i]=read();
	ans=n;
	for(int i=1;i<=n;i++)
    {
		while(st[top]>h[i])top--;
		if(st[top]==h[i])ans--;
		else st[++top]=h[i];
	}
	printf("%d",ans);
	return 0;
}

#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

inline int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n,m,ans,top;

int h[50005],st[50005];

int main()

{

n=read();m=read();

for(int i=1;i<=n;i++)

h[i]=read(),h[i]=read();

ans=n;

for(int i=1;i<=n;i++)

{

while(st[top]>h[i])top--;

if(st[top]==h[i])ans--;

else st[++top]=h[i];

}

printf("%d",ans);

return 0;

}

« 「BZOJ1628」[Usaco2007 Demo] City skyline 善良的hzwer »

hzwer.com _ Home | http://hzwer.com

「BZOJ1683」[Usaco2005 Nov] City skyline 城市地平线

Description

Input

Output

Sample Input

Sample Output

题解

分类目录

热门文章

Myfriends

近期评论