社区讨论

30pts

P2504[HAOI2006] 聪明的猴子参与者 4已保存回复 3

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
3 条
当前快照
1 份
快照标识符
@m40z8v2m
此快照首次捕获于
2024/11/28 15:12
去年
此快照最后确认于
2025/11/04 13:45
4 个月前
查看原帖
CPP
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10,dd=1e6+10;
struct node{
	int u,v,c;
}e[dd];
int n,m;
int h[N],xt[N],yt[N];
//并查集
int f[N];
void init(int k){
	for(int i=1;i<=k;i++){
		f[i]=i;
	}
}
int find(int x){
	if(f[x]==x)return x;
	return f[x]=find(f[x]);
}
void merge(int x,int y){
	int a=find(x),b=find(y);
	if(a==b)return;
	f[a]=b;
	return;
}

bool cmp(node x,node y){
	return x.c<y.c;
} 

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>m;
	for(int i=1;i<=m;i++){
		cin>>h[i];
	}
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>xt[i]>>yt[i];
	}
	int k=n*(n+1)/2,p=0;
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			p++;
			e[p].u=i;
			e[p].v=j;
			e[p].c=(xt[i]-xt[j])*(xt[i]-xt[j])+(yt[i]-yt[j])*(yt[i]-yt[j]);
		}
	}
	init(k);
	int maxn=-1,cnt=0;
	sort(e+1,e+1+k,cmp);
	for(int i=1;i<=k;i++){
		int a=e[i].u,b=e[i].v;
		if(find(a)==find(b))continue;
		merge(a,b);
		maxn=max(maxn,e[i].c);
		cnt++;
		if(cnt==n-1)break;
	}
	int sum=0;
	for(int i=1;i<=m;i++){
		if(h[i]*h[i]>=maxn)sum++;
	}
	cout<<sum<<"\n";
	return 0;
}

回复

3 条回复,欢迎继续交流。

正在加载回复...