Advertisement
Jasuse

Untitled

Dec 3rd, 2019
113
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.83 KB | None | 0 0
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <vector>
  4. int Nc, Rgc, Cpc;
  5. int arr[100000] = {0};
  6.  
  7. int checkCount(int kNum) {
  8.   int start = 0;
  9.   int end = 0;
  10.   int count = 0;
  11.   while (end + 1 < Nc) {
  12.     if (arr[end + 1] - arr[start] <= kNum) {
  13.       ++end;
  14.     } else {
  15.       ++start;
  16.     }
  17.     if (end - start + 1 == Cpc) {
  18.       ++count;
  19.       start = end + 1;
  20.       end = start;
  21.     }
  22.   }
  23.   return count;
  24. }
  25.  
  26. int main() {
  27.   std::cin >> Nc >> Rgc >> Cpc;
  28.  
  29.   for (int i = 0; i < Nc; ++i) {
  30.     std::cin >> arr[i];
  31.   }
  32.   std::sort(arr, arr + Nc);
  33.  
  34.   int lhs = -1;
  35.   int rhs = arr[Nc - 1] - arr[0];
  36.   int mid = 0;
  37.   int min = rhs;
  38.   while (lhs < rhs) {
  39.     mid = (lhs + rhs) / 2;
  40.     if (checkCount(mid) < Rgc) {
  41.       lhs = mid + 1;
  42.     } else {
  43.       rhs = mid;
  44.     }
  45.   }
  46.   std::cout << rhs << "\n";
  47. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement