题解 P5199【 [USACO19JAN]Mountain View】

Rbu_nas

2019-03-05 22:38:18

Solution

本题理解题意就很好写了,模拟思路很好想。 注意一下「山」是沿$x$轴正方向蔓延的,并不是排成一列然后站在队首观望山峰的,也就是说我们预处理一下等腰直角三角形的左端点和右端点,不要被大的山所覆盖就好了。然后由于是等腰直角三角形,计算端点也没啥好说的 ![](https://cdn.luogu.com.cn/upload/pic/53256.png) 剩下的就是模拟了,加了快读跑到了rk1: ```cpp #include <cstdio> #include <algorithm> using namespace std; #define gcc getchar template <typename T> inline void read(T&x) { x=0; bool f=true; char ck=gcc(); for( ; ck<'0'||ck>'9'; ck=gcc()) if(ck == '-') f=false; for( ; ck>='0'&&ck<='9'; ck=gcc()) x=(x<<1)+(x<<3)+(ck^48); x=f?x:-x; return ; } #define N 100003 int n, maxr, res; struct Node { int l, r; bool operator < (const Node&other) const { return (l != other.l) ? (l < other.l) : (r > other.r); } //按左端点作为关键字排序,如果一样那么只能看到大的山了 } ; Node a[N]; int main(void) { read(n); for(int i=1; i<=n; ++i) { int x, y; read(x), read(y); a[i].l=x-y, a[i].r=x+y; //简单的预处理,如果不是等腰直角三角形也一样作垂线用三角函数 } sort(a+1, a+n+1); for(int i=1; i<=n; ++i) if(a[i].r > maxr) ++res, maxr=a[i].r; //每一次更新最右端点,不超过maxr的则会被大山包含 printf("%d", res); return 0; } ```