ceva_megamind

ИОИП бинпоиск не заходит

Feb 15th, 2020
167
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.61 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. int main() {
  8.     int n;
  9.     double len;
  10.     cin >> n >> len;
  11.     vector<double> a(n);
  12.     for (int i = 0; i < n; i++) {
  13.         cin >> a[i];
  14.     }
  15.     sort(a.begin(), a.end());
  16.     double l = 0, r = 1e10, m, curx;
  17.     bool ans;
  18.     for (int i = 0; i < 100; i++) {
  19.         m = (l + r) / 2;
  20.         curx = 0;
  21.         ans = true;
  22.         for (int q=0; q<n; q++) {
  23.             curx += m;
  24.             if (curx < a[q]) {
  25.                 ans = false;
  26.                 break;
  27.             }
  28.             if (q + 1 < n && a[q + 1] < curx) {
  29.                 curx = a[q + 1];
  30.             }
  31.         }
  32.         if (curx>=len&&ans)
  33.             r = m;
  34.         else
  35.             l = m;
  36.     }
  37.     cout << r;
  38. }
Add Comment
Please, Sign In to add comment