Advertisement
MeehoweCK

Untitled

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