2022牛客暑假第一场

A-Villages: Landlines

题目链接

题意简述： 在一个一维空间里，有若干个建筑和一个电站，它们各自有一个坐标$x_{i}x\_i$和覆盖半径$r_{i}r\_i$。建筑与建筑、建筑与电站之间的连接需要通过电塔，电塔在建筑（电塔）覆盖范围内即直接连接。电塔之间的连接通过电线。电塔可以随意布局，每一个建筑和电站都要连接在整个系统里，求最少需要多少电线。

题目分析：

由于建筑和建筑之间、建筑和电站之间的连接方式是一样的，可以把电站也当作建筑处理。

显然，当若干个建筑有重叠覆盖区域，那么在这个重叠区上的电塔(可以不止一个）已经和它们每一个相连，即连接他们不需要消耗电线。

反之，如果建筑之间的覆盖区间有间隔，必须在两者之间建立至少两个电塔，并用电线连接电塔。

显然，既然电塔的位置是任意的，那么把电塔布局在区间边界，可以使得连接它们的电线最短。 以样例为例：

也就是电线的总长是各个覆盖区间所不能覆盖的地方。 那么，到这步这题就变成了区间合并问题！

如果你记得区间合并求并集长度的模板之类的，稍微改写一下这题就结束啦！

不太了解那么继续↓

我们观察一个合并了的独立区间例如样例中的后三个区间：

为了方便，用括号代表区间左右端点。

（ （ ） ）（ ）

既然这段区间是若干个区间合并在一起的，那么它的左右端点数量一定一致。知道最左的左端点和最右的右端点坐标，也就知道了这段区间的长度。

反过来看，从头开始读取区间节点，当读到相等数量的左右节点，由于区间的左右端点一定是成对出现的，那么这一定是一段连续区间。

（在例子中直接这样截取会把这段区间认为是两个区间，但它们的总长度和整个区间的长度一致，故而在长度处理中不用特殊考虑）

那么把每个节点按坐标排列好，就可以按顺序读取它们，并得到合并后的区间的长度了。用左右两个极端得到的距离减去总长，就能得到空缺的长度，这就是我们要的答案。

当然，在处理的时候也可以直接把空缺的区间加和：读取到完整的独立区间（左右节点个数相同）后，把答案加上下一个节点到这个节点的距离即可。

完整代码：

#include<iostream>
#include<algorithm>
#include<stdio.h>
using namespace std;
inline int read(){
	int x=0;
	char c=getchar();
	int flag=1;
	while(c<'0'||c>'9')if(c=='-')flag=0,c=getchar();
	while(c>='0'&&c<='9'){
		x=x*10+(c-'0');
		c=getchar();
	}
	if(flag==1)
	return x;
	else return x*(-1);
}
struct point{
	int x;
	int kind;//0左 1右
}p[400010];
bool cmp(point a,point b){
	return a.x<b.x;
}
int main(){
	int n;
	n=read();
	int stp=0;
	for(int i=0;i<n;i++){
		int x,r;
		x=read();
		r=read();
		p[stp].x=x-r;
		p[stp].kind=0;//左节点是坐标-r，右同理
		stp++;
		p[stp].x=x+r;
		p[stp].kind=1;
		stp++;
	}
	sort(p,p+stp,cmp);
	int cnt=0;
	int ans=0;
	for(int i=0;i<stp-1;i++){
		if(p[i].kind==0)cnt++;
		else cnt--;
		if(cnt==0){
        //到这个节点为止是一个独立区间，下一个节点到这个节点的距离就是两个区间之间的空隙
			ans+=p[i+1].x-p[i].x;
		}
	}
	
	cout<<ans;
	return 0;
}