分析

看到这道题，可以说被翻译明示这是贪心题。

我们把每条线段的起点和终点算出来之后，再按照右端点从小到大排序。

证明：按右端点升序排列可以得到最优值

把右端点从左向右排，使得右端点以后的区间能有更大的空间覆盖。

比如现在有 \(5\) 条线段，如下：

---
-
  ----
        -----
    ------

按右端点升序排序后：

-
---
  ----
    ------
        -----

最优解为：

-
  ----
         -----

如果按左端点升序排列，会发现什么？会发现我给的样例不好。

会发现答案还是一样。

那么如果把线段 \([1,3]\) 换成 \([2,5]\) 会这样（按左端点升序排列）：

-
 -----
  ----
    ------
        -----

按这个形式的最优解就为：

-
 -----

发现反例，所以得证。（伪证啊喂

代码

//2021/8/30

#include <iostream>

#include <cstdio>

#include <algorithm>

#define int long long

#define debug(c) cerr<<#c<<" = "<<c<<endl

namespace Newstd
{
	inline int read()
	{
		int x=0,f=1;char ch=getchar();
		while(ch<‘0‘ || ch>‘9‘)
		{
			if(ch==‘-‘)
			{
				f=-1;ch=getchar();
			}
		}
		while(ch>=‘0‘ && ch<=‘9‘)
		{
			x=x*10+ch-48;ch=getchar();
		}
		return x*f;
	}
	inline void print(int x)
	{
		if(x<0)
		{
			putchar(‘-‘);x=-x;
		}
		if(x>9)
		{
			print(x/10);
		}
		putchar(x%10+‘0‘);
	}
}

using namespace Newstd;

using namespace std;

const int ma=100005;

struct Node
{
	int l;
	
	int r;
};

Node node[ma];

inline bool cmp(Node x,Node y)
{
	return x.r<y.r;
}

#undef int

int main(void)
{
	#define int long long
	
	int n=read();
	
	for(register int i=1;i<=n;i++)
	{
		int x,L;
		
		scanf("%lld%lld",&x,&L);
		
		node[i].l=x-L;
		
		node[i].r=x+L;
	}
	
	sort(node+1,node+n+1,cmp);
	
	int now=node[1].r,ans=1;
	
	for(register int i=2;i<=n;i++)
	{
		if(node[i].l>=now)
		{
			now=node[i].r;
			
			ans++;
		}
	}
	
	printf("%lld\n",ans);
	
	return 0;
}

AT5748 Robot Arms 题解