社区讨论
143行代码爆零了,求查错
P2504[HAOI2006] 聪明的猴子参与者 2已保存回复 2
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 2 条
- 当前快照
- 1 份
- 快照标识符
- @mi6mlmhx
- 此快照首次捕获于
- 2025/11/20 07:20 4 个月前
- 此快照最后确认于
- 2025/11/20 07:20 4 个月前
CPP
#include<stdio.h>
#include<math.h>
struct mon
{
int x;
int y;
int v;
};
int father[10001];
int max(int a,int b)
{
return a>b?a:b;
}
int find(int x)
{
if(father[x]!=x)
father[x]=find(father[x]);
return father[x];
}
void qsortcommon(int a[],int l,int r)
{
int i,j,mid,p;
i=l;
j=r;
mid=a[(l+r)/2];
while(i<=j)
{
while(a[i]<mid)
i++;
while(a[j]>mid)
j--;
if(i<=j)
{
p=a[i];
a[i]=a[j];
a[j]=p;
i++;
j--;
}
}
if(l<j)
qsortcommon(a,l,j);
if(i<r)
qsortcommon(a,i,r);
}
void qsort(struct mon a[],int l,int r)
{
int i,j,mid;
struct mon p;
i=l;
j=r;
mid=a[(l+r)/2].v;
while(i<=j)
{
while(a[i].v<mid)
i++;
while(a[j].v>mid)
j--;
if(i<=j)
{
p=a[i];
a[i]=a[j];
a[j]=p;
i++;
j--;
}
}
if(l<j)
qsort(a,l,j);
if(i<r)
qsort(a,i,r);
}
inline int read()
{
int x=0,w=1;
char ch=getchar();
while(ch>'9'||ch<'0')
{
if(ch=='-')
w=-1;
ch=getchar();
}
while(ch<='9'&&ch>='0')
{
x=(x<<3)+(x<<1)+ch-'0';
ch=getchar();
}
return w*x;
}
int main()
{
struct mon a[10001];
int o=0,i,j,monkeys[10001],n,x[10001],y[10001],ans=0,s;
n=read();
for(i=1;i<=n;i++)
monkeys[i]=read();
qsortcommon(monkeys,1,n);
s=read();
for(i=1;i<=n;i++)
{
x[i]=read();
y[i]=read();
}
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
int tx=x[i]-x[j];
int ty=y[i]-y[j];
int ts;
tx*=tx;
ty*=ty;
ts=(int)sqrt(tx+ty);
o++;
a[o].x=i;
a[o].y=j;
a[o].v=s;
}
int k;
qsort(a,1,o);
int temp=0;
for(i=1;i<=o;i++)
{
int r1,r2;
r1=find(a[i].x);
r2=find(a[i].y);
if(r1!=r2)
{
k=max(s,a[i].v);
father[r1]=r2;
k++;
temp++;
}
if(temp==n-1)
break;
}
for(i=1;i<=n;i++)
if(monkeys[i]>k)
ans++;
else
break;
printf("%d\n",ans-1);
return 0;
}
回复
共 2 条回复,欢迎继续交流。
正在加载回复...