这道题一看最小值最大，很容易被误导进二分答案的思路，但实际上并不需要二分答案。
其实正解是最小生成树，我们先预处理出原图的最小生成树，因为要分k个部落，所以我们先把最小的n-k边先全部选走。因为我们用kruskal的话要用到并查集，这样我们就可以判断他们是否在同一部落中。然后我们再枚举剩下未选的边，再看这个边连接的两个端点是否在同一集合内，输出那个最先找到的值即可。复杂度就是krukal的复杂度O(klogn)，由于我们选不完所有边，还要比这个小一些。
代码如下：
#include<bits/stdc++.h>using namespace std;const int maxn=1e6+7;struct node{ int x,y; double val;}edge[maxn*3];double dist(int x,int xxx,int y,int yyy){ return (double)sqrt((x-xxx)*(x-xxx)*1.0+(y-yyy)*(y-yyy)*1.0);}bool cmp(node a,node b){ return a.val<b.val;}int fa[maxn];int get(int x){ if(x==fa[x]) return x; else return fa[x]=get(fa[x]);}int xx[maxn],yy[maxn];int n,k,cnt;void kruskal(){ int tot=0; for(int i=1;i<=cnt;i++){ int f1=get(edge[i].x); int f2=get(edge[i].y); if(f1!=f2){ fa[f1]=f2; tot++; if(tot==n-k) break; } } for(int i=n-k+1;i<=cnt;i++){ if(get(edge[i].x)!=get(edge[i].y)){ printf("%.2lf\n",edge[i].val); break; } }}int main(){ scanf("%d%d",&n,&k); for(int i=1;i<=n;i++) fa[i]=i; for(int i=1;i<=n;i++){ scanf("%d%d",&xx[i],&yy[i]); } for(int i=1;i<=n;i++){ for(int j=i+1;j<=n;j++){ edge[++cnt].x=i; edge[cnt].y=j; edge[cnt].val=dist(xx[i],xx[j],yy[i],yy[j]); } } sort(edge+1,edge+1+cnt,cmp); kruskal(); return 0;}
View Code
