609. Вода

Недавно Сергей пошел к колодцу за водой, но так и не вернулся. Он взял с собой n канистр, каждую из которых он полностью наполнил водой. Теперь Сергей хочет доставить их в свой загородный дом. Вот в этом и заключается проблема. За один раз Сергей может унести не более 2 канистр – у него ведь всего две руки. Более того, он может нести не более k литров воды.

Теперь Сергей стоит у колодца и думает, за какое минимальное число раз он может отнести всю воду домой, и может ли вообще. Помогите ему решить эту задачу.

Вход. В первой строке содержатся два целых числа n и k (1 ≤ n ≤ 10⁵). Во второй строке заданы n целых чисел – объемы канистр в литрах. Все входные числа положительные и не превышают 10⁹.

Выход. Если Сергей не сможет унести всю воду домой, выведите “Impossible”. Иначе выведите одно число – минимальное необходимое число раз.

Пример входа	Пример выхода
4 4 1 2 3 3	3

РЕШЕНИЕ

жадность

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

Если объем некоторой канистры больше k, то всю воду унести домой невозможно, выводим “Impossible”.

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

Пример

Рассмотрим пример из условия задачи. Объемы имеющихся канистр: 1, 2, 3, 3. За один раз Сергей может нести не более k = 4 литров воды. Сумма объемов наименьшей и наибольшей канистры равна 1 + 3 = 4, что не больше k. Следовательно в первый раз Сергей перенесет эти две канистры.

Остались канистры 2 и 3. Сумма объемов наименьшей и наибольшей канистры равна 2 + 3 = 5, что больше k. Следовательно во второй раз наибольшую канистру следует нести домой одну.

В третий раз Сергей заберет домой последнюю канистру объемом 2 литра.

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

Объемы канистр храним в массиве m.

vector<int> m;

Читаем входные данные.

v.resize(n);

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

scanf("%d", &v[i]);

Сортируем объемы канистр.

sort(v.begin(), v.end());

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

res = 0;

Установим два указателя: а на начало массива, b – на конец.

a = 0; b = v.size() - 1;

Если наибольшая канистра больше k, то унести всю воду невозможно.

if (v[b] > k)

{

printf("Impossible\n"); return 0;

}

Переносим воду.

while (a <= b)

{

Если сумма наименьшей и наибольшей канистры больше k, то за один раз можно унести только наибольшую канистру.

if (v[a] + v[b] > k) b--;

Иначе несем две канистры: наименьшую и наибольшую.

else { a++; b--; }

Плюс одна ходка за водой.

res++;

}

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

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

Python реализация

import sys

Читаем входные данные.

n, k = map(int, input().split())

v = list(map(int, input().split()))

Сортируем объемы канистр.

v.sort()

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

res = 0

Установим два указателя: а на начало массива, b – на конец.

a = 0

b = len(v) – 1

Если наибольшая канистра больше k, то унести всю воду невозможно.

if v[b] > k:

print("Impossible")

sys.exit(0)

Переносим воду.

while a <= b:

Если сумма наименьшей и наибольшей канистры больше k, то за один раз можно унести только наибольшую канистру.

if v[a] + v[b] > k:

b -= 1

else:

Иначе несем две канистры: наименьшую и наибольшую.

a += 1

b -= 1

Плюс одна ходка за водой.

res += 1

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

print(res)