Codeforces Round 907 (Div. 2) |
---|
Закончено |
Мальчик Смайло играет в новую игру! В игре есть $$$n$$$ орд монстров, в $$$i$$$-й орде $$$a_i$$$ монстров. Цель игры — уничтожить всех монстров. Для этого у вас есть два типа атак и счетчик комбо $$$x$$$, изначально равный $$$0$$$:
Ваша задача — зачистить всех монстров, то есть сделать так, чтобы ни в одной орде не осталось ни одного монстра. Смайло хочет как можно скорее победить, поэтому скажите, какое минимальное число атак можно применить?
В первой строке содержится единственное число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — число орд монстров.
Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — количества монстров в каждой орде.
Гарантируется, что сумма $$$n$$$ по всем тестовым наборам не превосходит $$$2 \cdot {10^5}$$$.
Для каждого набора входных данных выведите минимальное число атак, которое нужно, чтобы убить всех монстров.
441 3 1 141 2 1 163 2 1 5 2 421 6
4 4 11 5
В первом наборе входных данных можно применить атаку первого типа по одному разу на $$$1$$$-ю, $$$3$$$-ю и $$$4$$$-ю орду, затем добить атакой второго типа $$$2$$$-ю орду. Итого нужно $$$4$$$ атаки.
Во втором наборе входных данных можно применить атаку первого типа по одному разу на $$$1$$$-ю, $$$3$$$-ю орду, затем добить атакой второго типа $$$2$$$-ю орду, затем применить атаку первого типа один раз на $$$4$$$-ю орду. Итого нужно $$$4$$$ атаки.
В четвёртом наборе входных данных можно применить атаку первого типа один раз на $$$1$$$-ю орду, два раза на $$$2$$$-ю орду, затем применить один раз атаку второго типа на $$$2$$$-ю орду, затем применить один раз атаку первого типа на $$$2$$$-ю орду. Итого нужно $$$5$$$ атак.
Название |
---|