Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <map>
- using namespace std;
- int main() {
- int n, a;
- map <int, int> their_dishes; //номер блюда, количество блюд с таким номером
- map <int, int> longs; //длина неподеленного куска, количество таких кусков
- cin >> n;
- for (int i = 0; i < n; ++i) {
- cin >> a;
- their_dishes[a] ++;
- }
- multimap <int, int> dishes; //количество блюд с таким номером, номер блюда
- for (auto elem: their_dishes)
- dishes.insert({elem.second, elem.first});
- longs[(*dishes.rbegin()).first] = 1; //делаем 1 длинный кусок из блюд которых больше всего
- dishes.erase((*dishes.rbegin()).first); //убриаем эти блюда из списка (они все использованы)
- int count;
- while (not dishes.empty()) {
- count = (*dishes.rbegin()).first; //count - количество блюд которых больше всего на данный момент
- auto it = dishes.end();
- it--;
- dishes.erase(it, it); //убираем все такие блюда тк считаем, что далее используем их все
- int qur_big_count = (*longs.rbegin()).first, qur_count;
- while (count > 0) {
- if (count > qur_big_count) qur_count = qur_big_count; //если count больше то сначала поделим все наибольшие пополам
- else qur_count = count; //если count меньше то поделим максимальное количество наибольших пополам
- count -= qur_count;
- int c, b; //length of halfs
- c = (*longs.rbegin()).first / 2; //вычисляем длины половин наибольшего
- b = (*longs.rbegin()).first - c;
- while (qur_count != 0) { //делим наибольшие пополам, пока не кончатся разделители
- longs[(*longs.rbegin()).first]--; //убираем 1 наибольший
- longs[c]++;
- longs[b]++; //добавляем 2 половинки
- if (longs[(*longs.rbegin()).first] == 0) longs.erase((*longs.rbegin()).first); //если наибольшие длинные кончились, то убираем их
- if (longs.empty()) {
- cout << 0;
- return 0;
- }
- qur_count--;
- }
- if (longs.empty()) {
- cout << 0;
- return 0;
- }
- }
- if (longs.empty()) {
- cout << 0;
- return 0;
- }
- //если count меньше количества наибольших longs то
- // находим середину с округл вверх -> добавляем вместо count лонгов по count/2 бОльших и меньших половин
- //если больше то сначала алг а) для наибольших, далее для все меньших --остаются лишние -- ставим в начало
- //когда участков 0 - мы победили, ответ 0
- }
- if (not longs.empty()) {
- cout << (*longs.rbegin()).first;
- return 0;
- }
- else {
- cout << 0;
- return 0;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement