给你一些点（ <= 50），让你找到k个点，使得他们之间的最小距离最大。
思路：
求最小的最大，我们可以直接二分去枚举距离，但是要注意，不要去二分double找距离，要知道，最后的答案肯定是其中某个点的两点距离，所以我们直接把所有点的距离求出来，放一个数组里面，然后sort下，然后去二分这个数组的下标，根据下标找距离，这样可以节省点时间（这种情况这针对于某些题目，如果点非常多，n*(n-1)/2距离的种类是有可能很多，这样还不如直接二分double快点，毕竟二分是log级别的），二分的时候我们可以根据最大团来判断当前最大团是否大于等于k，来看当前距离是不是满足要求，在简单说一下在这个题目里用最大团要注意的东西，首先最大团是NP问题，求他是很费时间的，平时我常用的就是搜索+dp优化，hdu1530是模板题目，我自己看了最大团的思路后直接自己模拟一个4000+ms AC了，但是在这个题目里，直接各种TLE，因为自己模拟的那个没有dp优化，做这个题目必须dp优化，不然会死的很惨。还有就是有的人看到最大团，或者最大独立集元素个数就直接想着用 二分匹配去做（之前我就是）但是大家一直忽略了一个问题，就是二分匹配的前提是题目给的是二分图，大家经常忽略了题目给的是不是二分图，而直接套定义所以会直接 一遍匈牙利 然后各种wa。二分图的最大团，或者最大独立集可以 匈牙利 但是不是二分图的就直接是 NP问题,就只能用本方法去壳，但要记得dp优化什么的。
#include<stdio.h> #include<string.h> #include<math.h> #include<algorithm> #define N 60 using namespace std; typedef struct { double x ,y; }NODE; NODE node[N]; int n ,k ,Ans; int map[N][N] ,now[N]; int dp[N]; double dis[N][N] ,num[N*N]; void DFS(int x ,int sum) { if(sum > Ans) Ans = sum; if(Ans >= k) return; int able = 0; for(int i = x + 1 ;i <= n ;i ++) if(now[i]) able ++; if(able + sum <= Ans) return; int tnow[N]; for(int i = x + 1 ;i <= n ;i ++) tnow[i] = now[i]; for(int i = x + 1 ;i <= n ;i ++) { if(!tnow[i]) continue; if(dp[i] + sum <= Ans) continue; for(int j = x + 1 ;j <= n ;j ++) now[j] = tnow[j] & map[i][j]; DFS(i ,sum + 1); } } int jude(int mid) { for(int i = 1 ;i <= n ;i ++) for(int j = i + 1 ;j <= n ;j ++) if(num[mid] <= dis[i][j]) map[i][j] = map[j][i] = 1; else map[i][j] = map[j][i] = 0; Ans = dp[n] = 1; for(int i = n - 1 ;i >= 1 ;i --) { for(int j = 1 ;j <= n ;j ++) now[j] = map[i][j]; DFS(i ,1); dp[i] = Ans; if(Ans >= k) return 1; } return 0; } double get_dis(NODE a ,NODE b) { double x = (a.x - b.x) * (a.x - b.x); double y = (a.y - b.y) * (a.y - b.y); return sqrt(x + y); } int main () { int i ,j ,t; while(~scanf("%d %d" ,&n ,&k)) { for(i = 1 ;i <= n ;i ++) scanf("%lf %lf" ,&node[i].x ,&node[i].y); for(t = 0 ,i = 1 ;i <= n ;i ++) { for(j = i + 1 ;j <= n ;j ++) { dis[i][j] = dis[j][i] = get_dis(node[i] ,node[j]); num[++t] = dis[i][j]; } dis[i][i] = 0; } sort(num + 1 ,num + t + 1); int low = 1 ,up = t ,mid ,ans =1; while(low <= up) { mid = (low + up) >> 1; if(jude(mid)) { low = mid + 1; ans = mid; } else up = mid - 1; } printf("%.2lf " ,num[ans]); } return 0; }