MeehoweCK

Untitled

Dec 18th, 2018
141
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.74 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. bool zbior_rosnacy(vector<short> zbior)
  7. {
  8.     short poprzednia = zbior[0];
  9.     for(short i = 1; i < zbior.size(); ++i)
  10.     {
  11.         if(zbior[i] <= poprzednia)
  12.             return false;
  13.         poprzednia = zbior[i];
  14.     }
  15.     return true;
  16. }
  17.  
  18. int suma(vector<short> zbior)
  19. {
  20.     int wynik = 0;
  21.     for(short i = 0; i < (zbior.size() - 1); ++i)
  22.         wynik += zbior[i];
  23.     return wynik;
  24. }
  25.  
  26. bool utworz_nowy_zbior(vector<short> stary_zbior, vector<short>& nowy_zbior)
  27. {
  28.     short n = stary_zbior.size();       // obecna wielkosc zbioru
  29.     short wielkosc = suma(stary_zbior) + stary_zbior[n-1];
  30.     vector<short> nowy;
  31.     nowy.resize(n);
  32.  
  33.     for(short k = n-2; k >= 0; --k)     // k - poczatek modyfikowanego zbioru
  34.     {
  35.         for(short i = 0; i < n; ++i)
  36.             nowy[i] = stary_zbior[i];       // kopiowanie dotychczasowego zbioru
  37.         ++nowy[k];
  38.         for(short p = k+1; p < (n-1); ++p)      // pozycja obecnie modyfikowanej liczby
  39.             nowy[p] = nowy[p-1] + 1;
  40.         nowy[n - 1] = wielkosc - suma(nowy);
  41.         if(zbior_rosnacy(nowy))
  42.         {
  43.             // wczytanie nowego zbioru:
  44.             for(short i = 0; i < n; ++i)
  45.                 nowy_zbior[i] = nowy[i];
  46.             return true;
  47.         }
  48.     }
  49.  
  50.     // jezeli jestesmy tutaj, to znaczy, ze nalezy zwiekszyc zbior o 1
  51.     ++n;
  52.     nowy.resize(n);
  53.     for(short i = 0; i < (n-1); ++i)
  54.         nowy[i] = i + 1;
  55.     nowy[n-1] = wielkosc - suma(nowy);
  56.     if(zbior_rosnacy(nowy))
  57.     {
  58.         // wczytanie nowego zbioru:
  59.         nowy_zbior.resize(n);
  60.         for(short i = 0; i < n; ++i)
  61.             nowy_zbior[i] = nowy[i];
  62.         return true;
  63.     }
  64.     else
  65.         return false;       // brak kolejnego zbioru
  66. }
  67.  
  68. int main()
  69. {
  70.     short n, liczba;
  71.     int wynik = 32767;
  72.     vector<short> tablica;
  73.     cin >> n;
  74.  
  75.     tablica.resize(n+1);
  76.     for(short i = 0; i < n; ++i)
  77.         tablica[i] = 0;
  78.  
  79.     for(short i = 0; i < n; ++i)
  80.     {
  81.         cin >> liczba;
  82.         ++tablica[liczba];
  83.     }
  84.  
  85.     for(short i = 1; i < tablica.size(); ++i)
  86.     {
  87.         tablica[i] = i - tablica[i];
  88.         if(tablica[i] < 0)
  89.             tablica[i] = 0;
  90.     }
  91.  
  92.     // algorytm szukania zbiorΓ³w - najwazniejsza czesc!!!
  93.     vector<short> zbior;
  94.     zbior.resize(1);
  95.     zbior = {n};
  96.  
  97.     do
  98.     {
  99.         liczba = 0;
  100.         for(short i = 0; i < zbior.size(); ++i)
  101.         {
  102.             liczba += tablica[zbior[i]];
  103.             if(liczba >= wynik)
  104.                 break;
  105.         }
  106.  
  107.         if(liczba < wynik)
  108.             wynik = liczba;
  109.         if(wynik == 0)
  110.             break;
  111.     } while(utworz_nowy_zbior(zbior, zbior));
  112.  
  113.     cout << wynik;
  114.     return 0;
  115. }
Add Comment
Please, Sign In to add comment