二分搜索:
#include <iostream> #include <stdio.h> #include <math.h> #include <algorithm> #include <string.h> #include <string> #include <stdlib.h> #include <malloc.h> using namespace std; int n,m; int p[100100]; int c (int x)//判断是否符合条件 { int last = 0; int art; for (int i=1;i<m;i++) { art = last + 1; while (art < n && p[art]- p[last] < x) { art++; } if (art == n) return 0; last=art; } return 1; } int main () { while (scanf ("%d%d",&n,&m)!=EOF) { for (int i=0;i<n;i++) scanf ("%d",&p[i]); sort (p,p+n); int lf=0,ri=1000000,mid; for (int i=1;i<1000;i++) { mid = (lf + ri)/2; if (c (mid) ) { lf = mid; } else { ri = mid; } } printf("%d\n",lf); } return 0; }