Codeforces Round 802 (Div. 2) |
---|
Закончено |
Маленький Леон живет в лесу. Недавно он заметил, что некоторые деревья возле его любимой тропинки засыхают, а другие наоборот слишком увлажнены. Леон очень любит свой лес, поэтому решил научиться контролировать уровень влажности почвы, чтобы спасти деревья.
Возле тропинки растут $$$n$$$ деревьев, текущие уровни влажности которых заданы массивом $$$a_1, a_2, \dots, a_n$$$. Леон научился трем способностям, которые помогут ему осушать и поливать почву.
Леон хочет узнать минимальное число действий, которое необходимо совершить, чтобы каждое дерево имело уровень влажности равный $$$0$$$.
Первая строка теста содержит одно целое число $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$) — количество наборов входных данных. Затем следуют $$$t$$$ наборов входных данных.
В первой строке каждого набора входных данных вводится одно целое число $$$n$$$ ($$$1 \leq n \leq 200\,000$$$).
Во второй строке вводятся $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \leq a_i \leq 10^9$$$) — изначальные уровни влажности деревьев.
Сумма значений $$$n$$$ по всем наборам тестовых данных не превосходит $$$200\,000$$$.
Для каждого набора входных данных выведите одно целое число — минимальное число действий. Можно показать, что ответ всегда существует.
4 3 -2 -2 -2 3 10 4 7 4 4 -4 4 -4 5 1 -2 3 -4 5
2 13 36 33
В первом наборе входных данных достаточно $$$2$$$ раза применить операцию прибавления $$$1$$$ ко всему массиву.
Во втором наборе входных данных можно $$$4$$$ раза применить операцию вычитания на префиксе длины $$$3$$$ и получить массив $$$6, 0, 3$$$.
После этого $$$6$$$ раз применить операцию вычитания на префиксе длины $$$1$$$ и $$$3$$$ раза операцию вычитания на суффиксе длины $$$1$$$. Итого, количество действий составит $$$4 + 6 + 3 = 13$$$. Можно показать, что меньшим количеством действий обойтись нельзя, поэтому $$$13$$$ — это ответ.
Название |
---|