2995 楼房
时间限制: 1 s
空间限制: 256000 KB
题目等级 : 黄金 Gold
题解
题目描述 Description
地平线(x轴)上有n个矩(lou)形(fang)，用三个整数h[i],l[i],r[i]来表示第i个矩形：矩形左下角为(l[i],0)，右上角为(r[i],h[i])。地平线高度为0。在轮廓线长度最小的前提下，从左到右输出轮廓线。
输入描述 Input Description
第一行一个整数n，表示矩形个数
以下n行，每行3个整数h[i],l[i],r[i]表示第i个矩形。
输出描述 Output Description
第一行一个整数m，表示节点个数
以下m行，每行一个坐标表示轮廓线上的节点。从左到右遍历轮廓线并顺序输出节点。第一个和最后一个节点的y坐标必然为0。
样例输入 Sample Input
【样例输入】
2
3 0 2
4 1 3
【样例输入2】
5
3 -3 0
2 -1 1
4 2 4
2 3 7
3 6 8
样例输出 Sample Output
【样例输出】
6
0 0
0 3
1 3
1 4
3 4
3 0
【样例输出2】
14
-3 0
-3 3
0 2
1 2
1 0
2 0
2 4
4 4
4 2
6 2
6 3
8 3
8 0
数据范围及提示 Data Size & Hint
对于30%的数据，n<=100
对于另外30%的数据，n<=100000,1<=h[i],l[i],r[i]<=1000
对于100%的数据，1<=n<=100000,1<=h[i]<=10^9,-10^9<=l[i]<r[i]<=10^9
1 /*-----------------------------正确的题解---------------------------------*/
2 /*扫描线+堆
3 我们把每一个楼房的两边(墙壁)的信息记录下来，然后按照墙壁的横坐标排序(具体方法见代码)
4 ，当扫到楼房左边时，如果它是最高的，就把答案记录下来，否则入堆，
5 扫到楼房右边时，如果它与当前最高的一样高并且最高的只有一条线，记
6 录答案，删除对它对应的左边墙壁，否则删除左边墙壁信息，不进行其他操作。 */
7 #include<cstdio>
8 #include<queue>
9 #include<algorithm>
10 using namespace std;
11 #define N 100100
12 struct ss{
13 int h,l,r;
14 bool operator < (const ss &a) const{
15 if(l==a.l) return h>a.h;//双关键字排序
16 return l<a.l;
17 }
18 }e[N<<1];
19 struct node{
20 int h,r;
21 node(ss x){h=x.h,r=x.r;}
22 bool operator < (const node &a) const{
23 return h<a.h;/*按照高度排序是为了满足覆盖关系*/
24 }
25 };
26 int n,cnt;//记录点的个数
27 pair<int,int>ans[N<<2];//记录答案点的坐标,这个空间要开到n*4,因为可能有比较极端的情况，使每个矩形的两边都形成解
28 priority_queue<node>que;//大根堆
29 ss bfs(ss now,int x){//更新now，处理记录扫描后的矩形的右端点
30 while(!que.empty()){
31 node nown=que.top();que.pop();
32 if(nown.r>now.r){//有比它宽的，且比它矮的
33 if(nown.h!=now.h) ans[++cnt]=make_pair(now.r,now.h),ans[++cnt]=make_pair(now.r,nown.h);
34 now.r=nown.r;now.h=nown.h;
35 }
36 if(now.r>=x) return now;//*
37 }
38 //队列空说明：有断层
39 ans[++cnt]=make_pair(now.r,now.h),ans[++cnt]=make_pair(now.r,0);//断层左边的两个点
40 now.h=0;now.r=0x7fffffff;//now.h清零，now.r=inf为的是覆盖全区间，在*处起作用
41 return now;
42 }
43 void solve(){
44 ans[++cnt]=make_pair(e[1].l,0);ans[++cnt]=make_pair(e[1].l,e[1].h);//记录左边界答案
45 ss now=e[1];
46 for(int i=2;i<=n;i++){//总共分 ①②③ 三大情况，前两种比较直观，第三种比较难处理
47 if(now.h>=e[i].h&&now.r>=e[i].l) que.push(e[i]);//① 存入堆，做备用最高点（这里处理了包含的情况）
48 if(now.h<e[i].h&&now.r>=e[i].l){//②
49 que.push(now);//把比当前最高点低的点都存入堆，一个也不能漏
50 ans[++cnt]=make_pair(e[i].l,now.h);//较低点
51 now=e[i];
52 ans[++cnt]=make_pair(e[i].l,now.h);//较高点
53 }
54 if(now.r<e[i].l){//③
55 now=bfs(now,e[i].l);//判断一个矩形横穿e[i]这个矩形
56 if(now.h>=e[i].h&&now.r>=e[i].l) que.push(e[i]);
57 if(now.h<e[i].h&&now.r>=e[i].l){//断层和比他低的一起处理
58 que.push(now);//上边的now=bfs..和这里很好的处理了输出点坐标的顺序问题
59 ans[++cnt]=make_pair(e[i].l,now.h);
60 now=e[i];
61 ans[++cnt]=make_pair(e[i].l,now.h);
62 }
63 }
64 }
65 bfs(now,0x7fffffff);//遍历全区间做收尾工作：因为最后一个点的右边界不一定是所有元素的最右边界
66 //总结：只要最高点发生跃迁，就要记录答案
67 }
68 int main(){
69 scanf("%d",&n);
70 for(int i=1;i<=n;i++) scanf("%d%d%d",&e[i].h,&e[i].l,&e[i].r);
71 sort(e+1,e+n+1);//左端点升序排列
72 solve();
73 printf("%d\n",cnt);
74 for(int i=1;i<=cnt;i++) printf("%d %d\n",ans[i].first,ans[i].second);//因为记录是按顺序记录的，所以按顺序输出即可
75 return 0;
76 } 一开始没做过扫描线的题目，毫无思路。感觉情况很多。不好考虑，线段树又忘记怎么打了。只拿了特殊数据的30分。
这个题目的思路还是敢于大胆的一个一个的合并矩形，同时把合并中的所有情况都考虑到，这样就能AC了。
我的代码：
1 #define N 100100
2 #include<iostream>
3 using namespace std;
4 #include<cstdio>
5 #include<queue>
6 #include<algorithm>
7 int n;
8 struct Jx{
9 int h,l,r;
10 bool operator <(Jx P)
11 const{
12 return h<P.h;
13 }
14 }jx[N<<1];
15 priority_queue<Jx>Q;
16 int anssum=0;
17 pair<int,int>ans[N<<2];
18 bool cmp(Jx Q,Jx P)
19 {
20 if(Q.l<P.l) return true;
21 if(Q.l>P.l) return false;
22 return Q.h>P.h;
23 }
24 void input()
25 {
26 scanf("%d",&n);
27 for(int i=1;i<=n;++i)
28 scanf("%d%d%d",&jx[i].h,&jx[i].l,&jx[i].r);
29 }
30 Jx bfs(Jx now,int x)
31 {
32 Jx nown;
33 while(!Q.empty())
34 {
35 nown=Q.top();
36 Q.pop();
37 if(now.r<nown.r)
38 {
39 if(now.h!=nown.h)
40 {
41 ans[++anssum]=make_pair(now.r,now.h);
42 ans[++anssum]=make_pair(now.r,nown.h);
43 }
44 now=nown;
45 }
46 if(now.r>=x) return now;
47 }
48 ans[++anssum]=make_pair(now.r,now.h);
49 ans[++anssum]=make_pair(now.r,0);
50 now.l=now.r;
51 now.h=0;
52 now.r=(1<<31)-1;
53 return now;
54 }
55 void solve()
56 {
57 ans[++anssum]=make_pair(jx[1].l,0);
58 ans[++anssum]=make_pair(jx[1].l,jx[1].h);
59 Jx now=jx[1];
60 for(int i=2;i<=n;++i)
61 {
62 if(jx[i].h<=now.h&&jx[i].l<=now.r)
63 {
64 Q.push(jx[i]);
65 }
66 if(jx[i].h>now.h&&jx[i].l<=now.r)
67 {
68 Q.push(now);
69 ans[++anssum]=make_pair(jx[i].l,now.h);
70 ans[++anssum]=make_pair(jx[i].l,jx[i].h);
71 now=jx[i];
72 }
73 if(now.r<jx[i].l)
74 {
75 now=bfs(now,jx[i].l);
76 if(jx[i].h<=now.h&&jx[i].l<=now.r)
77 {
78 Q.push(jx[i]);
79 }
80 if(jx[i].h>now.h&&jx[i].l<=now.r)
81 {
82 Q.push(now);
83 ans[++anssum]=make_pair(jx[i].l,now.h);
84 ans[++anssum]=make_pair(jx[i].l,jx[i].h);
85 now=jx[i];
86 }
87 }
88 }
89 bfs(now,(1<<31)-1);
90 }
91 int main()
92 {
93 input();
94 sort(jx+1,jx+n+1,cmp);
95 solve();
96 printf("%d\n",anssum);
97 for(int i=1;i<=anssum;++i)
98 printf("%d %d\n",ans[i].first,ans[i].second);
99 return 0;
100 } ![用堆实现优先级队列（Priority Queue）[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)