6250. Варка овощей

Хитрость варки овощей состоит в том, чтобы все кусочки были примерно одинакового размера. Если они не являются таковыми, то маленькие кусочки получаются слишком мягкими, а крупные недоваренными. К счастью, Вы слышали о кухонном ноже, хотя предупреждения Ваших родителей об использовании острых инструментов до сих пор находятся в Вашей голове. Поэтому Вы хотите использовать его как можно меньше. Вы можете взять кусок овоща весом w и разрезать его произвольным образом на две части с весами w_left и w_right, где w_left + w_right = w. Эту операцию назовем "разрез".

Зная размеры имеющихся кусков овощей, определить наименьшее количество разрезов, после выполнения которых соотношение между наименьшим и наибольшим куском будет больше заданного порогового значения.

Вход. Начинается с действительного числа t (0.5 < t < 1) с 2 десятичными цифрами и натурального числа n (n ≤ 1000). Далее идут n целых положительных весов w₁, w₂, ..., w_n. Все веса меньше чем 10⁶.

Выход. Вывести минимальное количество разрезов, после выполнения которых соотношение между наименьшим и наибольшим куском будет больше t. Считайте, что число необходимых разрезов меньше 500. Чтобы избежать проблем с действительными числами, предположим, что оптимальный ответ для отношения t будет таким же, как и для отношения t + 0.0001.

Пример входа 1	Пример выхода 1
0.99 3 2000 3000 4000	6
Пример входа 2	Пример выхода 2
0.80 2 1000 1400	3

РЕШЕНИЕ

структуры данных - очередь с приоритетами

Анализ алгоритма

Куски всегда следует разрезать на равное количество частей. Изначально считаем, что каждый из них разрезан на 1 кусок. Для каждого куска будем хранить его вес weight и количество частей parts, на которое он на данный момент разрезан (то есть кусок храним в виде пары (weight, parts)). Например, во втором тесте следует разрезать первый кусок на две части, а второй на три:

Куски храним в max – куче, где они сортируются по убыванию веса их одной части (то есть значению weight / parts). Для приведенного примера куча содержит две пары: ((1000, 2), (1400, 3)), причем именно в таком порядке, так как размер одной части первого овоща составляет 500, а второго – 466.7.

Вычислим величину минимального куска minWeight. Пока его отношение к величине максимального куска (хранящегося на вершине кучи) будет меньше t, выполняем следующие действия: извлечем из кучи овощ, вес одного куска которого наибольший. Если овощ на данный момент разрезан на parts частей, то увеличим в нем число разрезов на 1 и снова занесем в кучу. После каждого разрезания пересчитаем значение minWeight.

Реализация алгоритма

Информацию о разрезах овощей храним в структуре vegetable: исходный кусок массой weight разделен на parts частей, причем вес одной части составляет weight / parts. По этому весу одной части и будем сортировать куски, реализуем соответствующий компаратор.

struct vegetable

{

double weight;

int parts;

vegetable(double weight, int parts) :

weight(weight), parts(parts) {};

int operator< (const vegetable &a) const

{

return weight / parts < a.weight / a.parts;

}

};

Сохраним куски в очереди с приоритетами heap.

priority_queue<vegetable> heap;

Основная часть программы. Читаем входные данные. Ищем вес минимального куска minWeight. Информацию о кусках заносим в очередь: изначально все они разделены на 1 часть.

scanf("%lf %d",&t,&n);

minWeight = 1e10;

for(i = 0; i < n; i++)

{

scanf("%lf",&w);

heap.push(vegetable(w,1));

if (w < minWeight) minWeight = w;

}

Количество разрезов подсчитываем в переменной cuts.

cuts = 0;

for(;;)

{

Берем овощ с максимальным весом одной части cur.weight / cur.parts.

vegetable cur = heap.top();

Если отношение весов минимальной minWeight и максимальной части не меньше t, то останавливаем процесс деления.

if (minWeight / (cur.weight / cur.parts) >= t) break;

heap.pop(); cuts++;

Увеличиваем количество разрезов в овоще cur.

cur.parts++;

Пересчитываем вес минимальной части.

minWeight = min(minWeight,cur.weight / cur.parts);

Заносим обновленный кусок в очередь.

heap.push(cur);

}

Выводим ответ.

printf("%d\n",cuts);