6249. Посадка деревьев

Фермер Джон недавно купил n саженцев деревьев, которые он хочет посадить во дворе своего дома. Чтобы посадить саженец Джону требуется 1 день. Для каждого дерева Джон точно знает, через сколько дней после посадки оно вырастет до полной зрелости. Джон хочет устроить вечеринку для своих друзей фермеров чтобы произвести на них впечатление. Но он хочет организовать ее только после того, как все деревья вырастут. Точнее, вечеринка может быть организована как можно раньше, но на следующий день после того как вырастет последнее дерево.

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

Вход. Первая строка содержит количество n (1 ≤ n ≤ 10⁵) саженцев. Следующая строка содержит n целых чисел t_i (1 ≤ t_i ≤ 10⁶), где t_i равно количеству дней, за которое вырастет i-ое дерево.

Выход. Вывести самый ранний день, в который можно провести вечеринку. Дни нумеруются 1, 2, 3, ... начиная с текущего момента.

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

РЕШЕНИЕ

жадность

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

Сажать выгодно первым дерево, которое дольше всего растет. Отсортируем времена роста деревьев по убыванию – в таком порядке и будем их сажать.

Пусть в i-ый день Джон садит дерево, которое будет расти t_i дней. Значит дерево будет расти с (i + 1)-го дня до (i + t_i)-го. Если i-ое дерево вырастет последним, то вечеринку можно провести в (i + t_i + 1)-ый день. Осталось найти максимум среди этих значений, который и будет ответом:

Пример

Слева рассмотрим случай, если сажать деревья будем в порядке 2, 3, 3, 4. Справа рассмотрен случай когда деревья высаживаются в убывающем (оптимальном) порядке времени их роста. Голубым цветом отмечен день посадки дерева.

При оптимальной высадке четырех деревьев вечеринку можно проводить в день номер , что равно

max(1 + 4 + 1, 2 + 3 + 1, 3 + 3 + 1, 4 + 2 + 1) = max(6, 6, 7, 7) = 7

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

Компаратор f используется для сортировки массива по убыванию.

int f(int a, int b)

{

return a > b;

}

Основная часть программы. Читаем входные данные. Вектор t содержит время в днях, за которые вырастут имеющиеся деревья. Поскольку дни нумеруются с 1, то и в массиве t числа будем хранить начиная с 1 индекса.

scanf("%d",&n);

t.resize(n+1);

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

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

Сортируем время роста деревьев по убыванию.

sort(t.begin()+1,t.end(),f);

Вычисляем самый ранний день res, в который можно провести вечеринку.

res = 0;

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

res = max(res,i + t[i] + 1);

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

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

Java реализация

import java.util.*;

public class Main

{

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

int n = con.nextInt();

Integer t[] = new Integer[n+1];

t[0] = 2000000000;

for(int i = 1; i <= n; i++)

t[i] = con.nextInt();

Arrays.sort(t,Collections.reverseOrder());

int res = 0;

for(int i = 1; i <= n; i++)

res = Math.max(res,i + t[i] + 1);

System.out.println(res);

con.close();

}

}