璟雯院

珺璟如晔,雯华若锦

用户工具

站点工具


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$:

  1. 当 $y_i > y_j$ 时,j点无法与i形成联通块;
  2. 当$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 由 温婕莺