1163. 【普及组模拟赛】投影(skyline) 

题目描述

   一天你对着眼前的景物拍了一张照，这个相机很特别，有建筑物的地方显示“X”，没有建筑物的地方显示为“.”,假设每个建筑都是块状的，照片长W(1<=W<=1,000,000),用N(1<=N<=50,000)对平面坐标(x,y)( 1 <= x <= W, 0<= y <= 500,000)描述照片中建筑物高度发生变化的位置,你的任务是计算出最少需要多少个建筑才能形成该照片。 如下图： 图片最少需要6个建筑，

输入

第一行: 两个空格隔开的整数N,W; 第2到N+1行:两个空格隔开的整数x和y，表示发生改变的点的坐标。输入中x是严格递增的而且第1个x一定是1。

输出

输出最少需要多少建筑才能形成该照片。

样例输入

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

样例输出

6

思路就是找高度不同的点，只要比前面高度高就加一，小的话就看以前有没有这个高度，没有就加一，然后就可以有结果了

 

const maxn=50000; var a,b:array[0..maxn] of longint; i,j,n,w,x,y,ans,p:longint; begin readln(n,w); fori:=1 to n do begin readln(x,y); while(p>0) and (a[p]>y) do dec(p); if((p=0) or (a[p]<y)) and (y>0) then begin inc(ans); inc(p); a[p]:=y; end; end; writeln(ans); end.