(栈的应用5.4.4)POJ 3044 City Skyline(本来是想用栈的,后来邪恶的用了数组)
/* * POJ_3044.cpp * * Created on: 2013年10月31日 * Author: Administrator */#include <iostream>#include <cstdio>#include <cstring>const int maxn = 50010;int x[maxn];int y[maxn];bool use[maxn];int main(){int n,m;while(scanf("%d%d",&n,&m)!=EOF){memset(use,false,sizeof(use));int i,j;for(i = 0 ; i < n ; ++i){scanf("%d%d",&x[i],&y[i]);}int ans = 0;for(i = n - 1 ; i >= 0 ; --i){//从后往前扫if(!y[i] || use[i]){continue;}for(j = i - 1 ; j >= 0 ; --j){if(y[j] == y[i]){//左邻顶点坐标的高度 == 当前坐标的高度,则证明他们是同一栋楼use[j] = true;}else if(y[j] < y[i]){//左邻顶点坐标的高度 < 当前顶点坐标的高度,是新的一栋楼的开始break;}}ans++;}printf("%d\n",ans);}return 0;}