Advertisement
Korotkodul

Покрытие

Oct 1st, 2023 (edited)
628
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.69 KB | None | 0 0
  1. #include <cmath>
  2. #include <iostream>
  3. #include <vector>
  4.  
  5. using std::cin;
  6. using std::cout;
  7. using std::max;
  8. using std::min;
  9. using std::string;
  10. using std::vector;
  11.  
  12. int inv = 0;
  13. int len;
  14. int knum;
  15. vector<int> ar;
  16.  
  17. vector<int> MergeSort(vector<int> ar) {
  18.   int len = ar.size();
  19.   if (len == 1) {
  20.     return ar;
  21.   }
  22.   vector<int> lt;
  23.   vector<int> rt;
  24.   for (int id = 0; id < len / 2; ++id) {
  25.     lt.push_back(ar[id]);
  26.   }
  27.   for (int id = len / 2; id < len; ++id) {
  28.     rt.push_back(ar[id]);
  29.   }
  30.   lt = MergeSort(lt);
  31.   rt = MergeSort(rt);
  32.   int ln = lt.size();
  33.   int rn = rt.size();
  34.   int lid = 0;
  35.   int rid = 0;
  36.   vector<int> res;
  37.   while (lid < ln || rid < rn) {
  38.     if (lid < ln && rid < rn) {
  39.       if (lt[lid] <= rt[rid]) {
  40.         res.push_back(lt[lid]);
  41.         lid++;
  42.       } else {
  43.         res.push_back(rt[rid]);
  44.         rid++;
  45.         inv += ln - lid;
  46.       }
  47.     } else if (lid < ln) {
  48.       res.push_back(lt[lid]);
  49.       lid++;
  50.  
  51.     } else if (rid < rn) {
  52.       res.push_back(rt[rid]);
  53.       rid++;
  54.     }
  55.   }
  56.   return res;
  57. }
  58.  
  59. bool Check(int md) {
  60.   int left = 0;
  61.   int cnt = knum;
  62.   for (int id = 1; id < len; ++id) {
  63.     if (ar[id] - ar[left] <= md) {
  64.       continue;
  65.     }
  66.     cnt--;
  67.     left = id;
  68.   }
  69.   return cnt >= 0;
  70. }
  71.  
  72. int main() {
  73.   std::ios::sync_with_stdio(false);
  74.   std::cin.tie(0);
  75.   std::cout.tie(0);
  76.   cin >> len >> knum;
  77.   ar.resize(len);
  78.   for (int& el : ar) {
  79.     cin >> el;
  80.   }
  81.   ar = MergeSort(ar);
  82.   int lt = 1;
  83.   int rt = ar[len - 1] - ar[0];
  84.   int md;
  85.   while (rt - lt > 1) {
  86.     md = (lt + rt) / 2;
  87.     bool ok = Check(md);
  88.     if (ok) {
  89.       rt = md;
  90.     } else {
  91.       lt = md;
  92.     }
  93.   }
  94.   cout << rt;
  95. }
  96.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement