icpc:problems:usaco20open_the_moo_particle_s
problems | |
---|---|
名称 | The Moo Particle S |
题目编号 | USACO20OPEN_S3 |
题目链接 | luogu.com.cn/… |
来源 | USACO |
算法分类 | 栈 |
难易程度 | 一般般 |
The Moo Particle S
想法
对可以互相链接的点进行相连,可以发现同属1个联通块的点最终可以缩为1个点。
将整个点集排序,考虑$i < j$:
- 当 $y_i > y_j$ 时,j点无法与i形成联通块;
- 当$y_i < y_j$时,j点可以与i形成联通块,并且$[y_j, y_i]$范围内的点可以由$y_j$作为桥梁形成联通块。
故使用栈维护单调递减的y。当一个较大的y进入栈时,保留栈顶,并将比y小的出栈。最后统计栈内元素数量即可。
代码实现
#include<cstdio> #include<algorithm> using namespace std; const int N = 1e5+10; struct node { int x, y; friend bool operator<(const node a, const node b) { return a.x < b.x || (a.x == b.x && a.y < b.y); } }; node line[N]; int s[N], top; int main() { int n; scanf("%d", &n); for (int i = 0; i < n; ++i) scanf("%d %d", &line[i].x, &line[i].y); sort(line, line + n); for (int i = 0; i < n; ++i) { if(top == 0 || s[top] > line[i].y) { s[++top] = line[i].y; } else { while(top > 1 && s[top-1] <= line[i].y) { s[top-1] = s[top]; top--; } } } printf("%d", top); return 0; }
/app/www/public/data/pages/icpc/problems/usaco20open_the_moo_particle_s.txt · 最后更改: 2023/06/03 13:34 由 温婕莺