fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. /*
  5. QUESTION IN SIMPLE WORDS
  6. ------------------------
  7. Some stations are already placed on a straight line.
  8.  
  9. We are allowed to add exactly K new repeaters at integer positions.
  10.  
  11. After adding them, we want the largest gap between any two consecutive
  12. stations to be as small as possible.
  13.  
  14. Goal:
  15. Return the minimum possible value of that largest gap.
  16.  
  17. ------------------------------------------------------------
  18. BRUTE FORCE IDEA
  19. ------------------------------------------------------------
  20. Try every possible way to place K repeaters.
  21.  
  22. For each placement:
  23. - sort all station positions
  24. - compute all consecutive gaps
  25. - take the maximum gap
  26. - keep the best answer
  27.  
  28. ------------------------------------------------------------
  29. WHY BRUTE FORCE IS TOO SLOW
  30. ------------------------------------------------------------
  31. There are too many possible integer positions.
  32.  
  33. The number of placements becomes huge very quickly.
  34.  
  35. ------------------------------------------------------------
  36. OPTIMIZED IDEA
  37. ------------------------------------------------------------
  38. This is a "minimize the maximum" problem.
  39.  
  40. That pattern usually suggests:
  41. binary search on the answer.
  42.  
  43. Suppose we guess the answer = gapLimit.
  44.  
  45. Then we can check:
  46. How many repeaters are needed so that every original gap becomes <= gapLimit?
  47.  
  48. If needed repeaters <= K, then this gapLimit is possible.
  49. So we try smaller.
  50. Otherwise, we need a bigger answer.
  51. */
  52.  
  53. long long minimumLargestGap(vector<int> pos, int k) {
  54.     sort(pos.begin(), pos.end());
  55.  
  56.     if ((int)pos.size() <= 1) return 0;
  57.  
  58.     // Returns how many extra repeaters we need
  59.     // if maximum allowed gap is gapLimit.
  60.     auto need = [&](long long gapLimit) -> long long {
  61.         long long extra = 0;
  62.  
  63.         for (int i = 1; i < (int)pos.size(); i++) {
  64.             long long gap = pos[i] - pos[i - 1];
  65.  
  66.             /*
  67.             Example:
  68.             positions: 1 and 10
  69.             gap = 9
  70.  
  71.             If gapLimit = 3,
  72.             we need 2 extra repeaters to split 9 into 3,3,3.
  73.  
  74.             Formula:
  75.             (gap - 1) / gapLimit
  76.             */
  77.             extra += (gap - 1) / gapLimit;
  78.         }
  79.  
  80.         return extra;
  81.     };
  82.  
  83.     long long lo = 1;
  84.     long long hi = 0;
  85.  
  86.     // Maximum original gap is a safe upper bound.
  87.     for (int i = 1; i < (int)pos.size(); i++) {
  88.         hi = max(hi, 1LL * pos[i] - pos[i - 1]);
  89.     }
  90.  
  91.     // Binary search smallest feasible answer
  92.     while (lo < hi) {
  93.         long long mid = (lo + hi) / 2;
  94.  
  95.         if (need(mid) <= k) {
  96.             hi = mid;
  97.         } else {
  98.             lo = mid + 1;
  99.         }
  100.     }
  101.  
  102.     return lo;
  103. }
  104.  
  105. int main() {
  106.     vector<int> pos = {1, 10};
  107.     int k = 2;
  108.  
  109.     cout << minimumLargestGap(pos, k) << '\n';
  110.     return 0;
  111. }
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
3
https://ideone.com/PMzxZp
language:
C++14 (gcc 8.3)
created:
4 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!