编译器里能过样例交上全是Re
查看原帖
编译器里能过样例交上全是Re
941729
peiyinsong楼主2024/4/14 18:20
#include<bits/stdc++.h>
using namespace std;
int a[101][101];
struct dia{
	double x,y;
}dian[10000];
struct bia{
	long long qi,zhi;
	double w;
}bian[1000005];
int fa[305];
int find(int a){
	if(fa[a]==a)return a;
	else return find(fa[a]);
}
int he(int a,int b){
	fa[find(a)]=find(b);
}
bool cmp(bia a,bia b){
	return a.w<b.w;
}
int monkey[1000];
int main()
{
int n;
cin>>n;
for(int i=0;i<=304;i++)fa[i]=i;
for(int i=0;i<50000;i++)bian[i].w=0;
for(int i=0;i<n;i++)
	cin>>monkey[i];

int m;
cin>>m;
for(int i=1;i<=m;i++)
	cin>>dian[i].x>>dian[i].y;

int qwe=0;
for(int i=1;i<=m;i++){
	for(int j=i;j<=m;j++){
		if(i!=j){
		bian[qwe].qi=i;
		bian[qwe].zhi=j;
		bian[qwe].w=sqrt((dian[i].x-dian[j].x)*(dian[i].x-dian[j].x)+(dian[i].y-dian[j].y)*(dian[i].y-dian[j].y));
		qwe++;
		 } 
	}
}

sort(bian,bian+qwe,cmp);
double maxx=0,summ=0;
for(int i=0;i<qwe;i++)
{
	if(find(bian[i].qi)!=find(bian[i].zhi))
	{
		maxx=max(maxx,bian[i].w);
		he(bian[i].qi,bian[i].zhi);
		summ++;
	}
}
int ans=0;
for(int i=0;i<n;i++)
if(monkey[i]>=maxx)
ans++;


cout<<ans;
return 0;
}


2024/4/14 18:20
加载中...