Решение задачи Лиса и коробки с Codeforces

Без пояснения   Просмотров: 1327

У лисы Сиель в комнате есть n коробок. Все коробки имеют одинаковый размер и вес, но могут иметь различную прочность. Формально, i-ая коробка может выдержать не больше x i коробок на себе (будем называть x i прочностью коробки).

Так как у всех коробок одинаковый размер, Сиель не может поставить больше одной коробки непосредственно на некоторую коробку. Предположим, что у Сиель есть три коробки: у первой прочность 2, у второй прочность — 1, и у третьей — прочность 1. Нельзя одновременно поставить вторую и третью коробку прямо на первую. Но можно поставить вторую коробку прямо на первую, а затем третью коробку прямо на вторую. Назовем такое сооружение из коробок стопкой.


Лиса Сиель хочет соорудить стопки изо всех коробок. В каждой стопке может быть несколько коробок, но нельзя ставить больше x i коробок на i-ую коробку. Какое минимальное количество стопок может построить Сиель, используя все коробки?

Код 

#include <iostream>
#include <algorithm>

using namespace std;

int a[105], n, i, kol;

int main()
{
    cin >> n;
    for(i = 0; i < n; i++) cin >> a[i];

    sort(a + 0, a + n);

    for(i = 0; i < n; i++)
        if (kol * a[i] + kol <= i) kol++;

    cout << kol << endl;

    return 0;
}

         

Администратор Photo Автор: Администратор



Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться



info@mycod.net   Карта сайта   Правообладателям
Заявка на расчет
×

или напишите нам прямо сейчас:

Написать в MAX
Написать в Telegram
Написать в WhatsApp