社区讨论
50分求助 貌似不是init 的问题(我看了上一个50分……)
P2504[HAOI2006] 聪明的猴子参与者 2已保存回复 3
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 3 条
- 当前快照
- 1 份
- 快照标识符
- @lo3487tz
- 此快照首次捕获于
- 2023/10/24 00:32 2 年前
- 此快照最后确认于
- 2023/10/24 00:32 2 年前
CPP
#include<bits/stdc++.h>
using namespace std;
struct www{
int l,r;
double w;
};
int ma[510],fa[510];
www k[1000010];
int a[1010],b[1010];
int n,m;
double dis(int x,int y){
double xx=x*x*1.0;
double yy=y*y*1.0;
return sqrt(xx+yy);
}
int f(int x){
if(fa[x]==x) return x;
return fa[x]=f(fa[x]);
}
bool he(int x,int y){
if(f(x)==f(y)) return 0;
fa[f(y)]=f(x);
return 1;
}
int cnt=0;
bool cmp(www x,www y){
return x.w<y.w;
}
double lll=-0x7fffffff;
void kuls(){
sort(k+1,k+cnt+1,cmp);
for(int i=1;i<=cnt;i++){
if(he(f(k[i].l),f(k[i].r))){
lll=max(lll,k[i].w);
}
}
}
int main(){
cin>>m;
for(int i=1;i<=m;i++){
cin>>ma[i];
}
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
cin>>b[i];fa[i]=i;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i==j) continue;
k[++cnt].l=i;
k[cnt].r=j;
k[cnt].w=dis(a[i]-a[j],b[i]-b[j]);
}
}
kuls();
int ans=0;
for(int i=1;i<=m;i++){
if(ma[i]>=lll) ans++;
}
cout<<ans;
}
回复
共 3 条回复,欢迎继续交流。
正在加载回复...