Advertisement
Guest User

Untitled

a guest
Jan 24th, 2020
140
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.82 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <map>
  4. using namespace std;
  5.  
  6. int main() {
  7.     int n, a;
  8.     map <int, int> their_dishes;                        //номер блюда, количество блюд с таким номером
  9.     map <int, int> longs;                               //длина неподеленного куска, количество таких кусков
  10.  
  11.     cin >> n;
  12.     for (int i = 0; i < n; ++i) {
  13.         cin >> a;
  14.         their_dishes[a] ++;
  15.     }
  16.     multimap <int, int> dishes;                             //количество блюд с таким номером, номер блюда
  17.  
  18.  
  19.     for (auto elem: their_dishes)
  20.         dishes.insert({elem.second, elem.first});
  21.  
  22.  
  23.     longs[(*dishes.rbegin()).first] = 1;              //делаем 1 длинный кусок из блюд которых больше всего
  24.     dishes.erase((*dishes.rbegin()).first);            //убриаем эти блюда из списка (они все использованы)
  25.  
  26.     int count;
  27.     while (not dishes.empty()) {
  28.         count = (*dishes.rbegin()).first;             //count - количество блюд которых больше всего на данный момент
  29.         auto it = dishes.end();
  30.         it--;
  31.         dishes.erase(it, it);                        //убираем все такие блюда тк считаем, что далее используем их все
  32.  
  33.         int qur_big_count = (*longs.rbegin()).first, qur_count;
  34.  
  35.         while (count > 0) {
  36.             if (count > qur_big_count) qur_count = qur_big_count; //если count больше то сначала поделим все наибольшие пополам
  37.             else qur_count = count;                               //если count меньше то поделим максимальное количество наибольших пополам
  38.             count -= qur_count;
  39.  
  40.             int c, b; //length of halfs
  41.             c = (*longs.rbegin()).first / 2;                      //вычисляем длины половин наибольшего
  42.             b = (*longs.rbegin()).first - c;
  43.  
  44.             while (qur_count != 0) {                              //делим наибольшие пополам, пока не кончатся разделители
  45.                 longs[(*longs.rbegin()).first]--;                 //убираем 1 наибольший
  46.                 longs[c]++;
  47.                 longs[b]++;                                       //добавляем 2 половинки
  48.                 if (longs[(*longs.rbegin()).first] == 0) longs.erase((*longs.rbegin()).first);  //если наибольшие длинные кончились, то убираем их
  49.                 if (longs.empty()) {
  50.                     cout << 0;
  51.                     return 0;
  52.                 }
  53.                 qur_count--;
  54.             }
  55.             if (longs.empty()) {
  56.                 cout << 0;
  57.                 return 0;
  58.             }
  59.         }
  60.         if (longs.empty()) {
  61.             cout << 0;
  62.             return 0;
  63.         }
  64.         //если count меньше количества наибольших longs то
  65.         // находим середину с округл вверх -> добавляем вместо count лонгов по count/2 бОльших и меньших половин
  66.         //если больше то сначала алг а) для наибольших, далее для все меньших --остаются лишние -- ставим в начало
  67.         //когда участков 0 - мы победили, ответ 0
  68.     }
  69.     if (not longs.empty()) {
  70.         cout << (*longs.rbegin()).first;
  71.         return 0;
  72.     }
  73.     else {
  74.         cout << 0;
  75.         return 0;
  76.     }
  77. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement