自动搬运

查看原文

来自洛谷，原作者为

	Alex_Wei **

搬运于2025-08-24 22:08:09，当前版本为作者最后更新于2019-03-15 19:47:49，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

$USACO\ 19JAN\ T3\ Mountain\ View$

虽然看起来比较难，但仔细想想应该就可以找到答案了

思路：

$1.$ 计算出每座山在 $x$ 轴上的左端点 $x-y$ 和右端点 $x+y$，然后按照左端点从小到大，左端点相同右端点从大到小的方法排序

$2.$ 从左到右遍历所有的山，如果当前的山的右端点大于之前所有山的右端点，则答案 $+1$

$3.$ 为什么？分两种情况讨论

$3.1$ 当这座山的右端点不大于之前最大的右端点，那么这座山一定能被之前右端点最大的那座山覆盖，如图

$3.2$ 当这座山的右端点大于之前最大的右端点

$3.2.1$ 在这座山之前没有能够覆盖它的山（因为这座山的右端点大于之前所有山的右端点）

$3.2.2$ 在这座山之后没有能够覆盖它的山（因为接下来的山要么左端点比这座山大，要么右端点比他小）

$3.2.3$ 综上，得出这座山不会被覆盖，如图

代码：

#include<bits/stdc++.h>
using namespace std;
struct node{
	int l,r;
}m[100100];
int n,w,s,x,y;
int cmp(node a,node b){return a.l<b.l||(a.l==b.l&&a.r>b.r);}//排序方法
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)cin>>x>>y,m[i].l=x-y,m[i].r=x+y;//算出左右端点
	sort(m+1,m+n+1,cmp);
	for(int i=1;i<=n;i++)if(m[i].r>w)s++,w=m[i].r;//如果大于当前所有山的右端点，答案+1，更新最大右端点
	cout<<s;
	return 0;
}

珍爱生命，远离抄袭！

如果有错误或建议欢迎在右侧->评论区指正或私信给我，谢谢！

求赞QAQ

$Update \ 2019.6.30\ \text{修改一处笔误，美化排版}$