二分，正反都扫一遍不连续K个不符条件即可

 

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #define INF 0x3f3f3f3f3f3f3f3f 6 using namespace std; 7 typedef long long LL; 8  9 const int maxn = 2e5 + 10;10 int A[maxn];11 int ans[maxn];12 int N, K;13 14 bool ck(int x) {15     int cnt = K - 1;16     for (int i = 0; i < N + 1 - K; i++) {17         if (A[i + K - 1] - A[i] > x) {18             cnt++;19         } else {20             cnt = 0;21         }22         if (cnt == K) return false;23     }24     cnt = K - 1;25     for (int i = N - 1; i >= K - 1; i--) {26         if (A[i] - A[i - K + 1] > x) {27             cnt++;28         } else {29             cnt = 0;30         }31         if (cnt == K) return false;32     }33     return true;34 }35 36 int main() {37     scanf("%d%d", &N, &K);38     for (int i = 0; i < N; i++) {39         scanf("%d", &A[i]);40     }41     sort(A, A + N);42     int dn = 0, up = A[N - 1] - A[0] + 1;43     while (dn < up - 1) {44         int mid = (up - dn) / 2 + dn;45         if (ck(mid)) {46             up = mid;47         } else {48             dn = mid;49         }50     }51     printf("%d\n", dn == 0 ? dn : up);52     return 0;53 }54 55 56 /*57 458 259 -1 2 4 10060 */