SHARE
TWEET

Untitled

a guest Mar 19th, 2019 66 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. bool check(int n, int k, int diff, int a[])
  6. {
  7.     vector <bool> dp(n); // da li ucenik moze uzeti grupu za sebe
  8.                         // a da su svi ostali ispod njegove grupe dodjeljeni nekoj od grupa
  9.     int last = -1;
  10.     for(int i = k - 1; i < n; i++)
  11.     {
  12.         int low = 0, high = i - k + 1;
  13.         while(low < high)
  14.         {
  15.             int pivot = (low + high) / 2;
  16.             if(a[i] - a[pivot] > diff) low = pivot + 1;
  17.             else high = pivot;
  18.         }
  19.         // low - najlaksi ucenik koji ispunjava kriterije da bude u grupi sa trenutnim
  20.         // (udaljeni su minimalno k polja)
  21.         if(a[i] - a[low] > diff) // trenutni ucenik nema dovoljno ljudi laksih od njega za formiranje grupe(manje od k - 1 laksih od njega)
  22.         {
  23.             continue;
  24.         }
  25.         if(low == 0) dp[i] = 1; // svi ucenici laksi od trenutnog mogu sa njim u grupu
  26.         else if(dp[low - 1] || last > low - 1) dp[i] = 1; // najtezi ucenik koji ne moze sa trenutnim u grupu moze da pokrije sve lakse od sebe
  27.                                                         // ili postoji ucenik (last, a[last] > a[low]) koji moze da pokrije sve prije sebe
  28.                                                         // pri cemu trenutnom uceniku ostaje dovoljno ljudi za grupu[od (last + 1) do (i - 1)]
  29.  
  30.         if(dp[i - k + 1]) last = i - k + 1; // gledamo da li postoji novi ucenik koji pokriva sve ispred sebe i ostavlja dovoljno studenata za grupu sljedecem uceniku po tezini
  31.     }
  32.     return dp[n - 1]; // uslov: posljednji ucenik formira svoju grupu i svi ostali ucenici su dodjeljeni grupama pri cemu je diff maksimalna razlika tezina ucenika iz iste grupe
  33. }
  34.  
  35. int main()
  36. {
  37.     int n, k;
  38.     cin >> n >> k;
  39.     int a[n];
  40.     for(int i = 0; i < n; i++)
  41.     {
  42.         cin >> a[i];
  43.     }
  44.     sort(a, a + n); // sortirati ucenike po rastucem redoslijedu njihovih tezina
  45.     int low = 0, high = a[n - 1] - a[0];
  46.     while(low < high)
  47.     {
  48.         int pivot = (low + high) / 2;
  49.         if(check(n, k, pivot, a)) high = pivot; // ucenici se mogu rasporediti u grupe ne manje od k clanova
  50.                                                 // gdje je pivot najveca dozvoljena razlika tezina unutar jedne grupe
  51.         else low = pivot + 1;
  52.     }
  53.     cout << low << endl; // najniza moguca razlika tezina
  54.     return 0;
  55. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top