题解 P5199 【[USACO19JAN]Mountain View】
Alex_Wei
·
·
题解
USACO\ 19JAN\ T3\ Mountain\ View
虽然看起来比较难，但仔细想想应该就可以找到答案了
思路：
$2.$ 从左到右遍历所有的山，**如果当前的山的右端点大于之前所有山的右端点，则答案 $+1$**
### $3.$ 为什么？分两种情况讨论
$3.1$ 当这座山的右端点不大于之前最大的右端点，那么这座山**一定能被之前右端点最大的那座山覆盖**，如图
#### $3.2$ 当这座山的右端点大于之前最大的右端点
$3.2.1$ 在这座山之前没有能够覆盖它的山（因为这座山的右端点大于之前所有山的右端点）
#### $3.2.2$ 在这座山之后没有能够覆盖它的山（因为接下来的山要么左端点比这座山大，要么右端点比他小）
$3.2.3$ 综上，得出这座山不会被覆盖，如图
### 代码：
```cpp
#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{修改一处笔误，美化排版}