自动搬运

查看原文

来自洛谷，原作者为

	InchTree **

搬运于2025-08-24 21:31:43，当前版本为作者最后更新于2020-04-02 12:56:01，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

论如何将一道“提高+”的题目写成“普及-”

关于“提高+”级别的做法（扫描线+线段树+离散化）题解区的各路大神各显神通，已经讲解得很详细了。对于像我一样刚学习扫描线、线段树、离散化的人来说是一道不错的综合入手题（其实还是建议这几种算法分开学）。

不过在赛场上，能想到一些代码简洁而又能保证正确率的算法何乐不为？

(以下为正文)

最简单的想法就是：记录下轴上每个点上建起的楼房高度的最大值。怎么记录呢？懒得打线段树的话那就暴力咯：

while(scanf("%d%d%d",&a,&h,&b)!=EOF) 
	for(i=a;i<=b;++i) H[i]=max(H[i],h); 

应该很多人都想到了但怕T就不敢写，算一下时间复杂度：5000×10000=5e7<1e8，加之这题常数较小，应该是能过的（实际上能用4ms以内时间通过所有该题的测试点 ）

然后很容易想到奇数点和偶数点总是成对出现的（废话），每次造成两点出现的原因都是最大高度的变化引起的，所以我们只需从坐标0到10000线性枚举一遍，如果该点的高度与上一点有差距，就等于新增了两个点，将即它们横(纵)坐标输出即可：

#include<bits/stdc++.h>
using namespace std;
int H[10005];
int main(){
	register int i,a,b,h;
	while(scanf("%d%d%d",&a,&h,&b)!=EOF) 
		for(i=a;i<=b;++i) H[i]=max(H[i],h); 
	for(i=1,h=0;i<1e4;++i)
		if(h!=H[i])
			h=H[i],printf("%d %d ",i,H[i]);
	return 0;
}

想到这，很开心地就把代码提交了，于是就WA了……(20分)

原因在哪？在点与点间的缝隙。

e.g.如果有两个房子的三元组是[1,10,3]与[4,10,6],显然区间[3，4]内存在一个缝隙，如果按刚才的算法，缝隙造成的四个点就被忽略了。

怎么改呢？有些人用的是±0.5的做法，个人觉得太麻烦了，其实只要把代码第7行的"<="改成"<"就行了。（至于为什么就留给大家思考下）

以下奉上简短的AC代码：

#include<bits/stdc++.h>
using namespace std;
int H[10005];
int main(){
	register int i,a,b,h;
	while(scanf("%d%d%d",&a,&h,&b)!=EOF) 
		for(i=a;i<b;++i) H[i]=max(H[i],h); 
	for(i=1,h=0;i<1e4;++i)
		if(h!=H[i])
			h=H[i],printf("%d %d ",i,H[i]);
	return 0;
}

//第一次写题解，所以选了较为简单的题目试一下手，如有问题我会尽快改正。