Первое, на что я обратил внимание — на то, что в условии сказано, что мы хотим в итоге сделать так, чтобы все элементы стали равны некоторому числу $$$x$$$, то есть $$$a_1 = a_2 = \ldots = a_n = x$$$. В таких ситуациях мне удобно зафиксировать у себя в голове это число $$$x$$$. Дальше, я должен задать себе вопрос. Каким образом должны выглядеть операции, чтобы в итоге все элементы стали равны $$$x$$$?

Во всех таких операциях я должен выбрать зафиксированный $$$x$$$, потому что сама операция как-бы приближает все числа к этому числу. Хорошо, допустим я знаю $$$x$$$. Хорошо, теперь я смотрю на саму операцию. В условии сказано, что она приближает все $$$a_i$$$ к $$$x$$$, причем все элементы не зависят друг от друга. Тогда через сколько операций число $$$a_i$$$ станет равно $$$x$$$?

Через $$$|a_i - x|$$$ операций. Тогда через сколько операций все элементы станут равны $$$x$$$?

Через $$$\max\limits_{i=1}^{n}|a_i - x|$$$. Хорошо. Дальше, я смотрю на ограничения задачи. Я вижу, что $$$1 \le a_i \le 1000$$$. А еще $$$2 \le n \le 1000$$$. Тогда какие $$$x$$$ мне нужно перебрать?

Мне нужно перебрать $$$1 \le x \le 1000$$$, потому что сами $$$1 \le a_i \le 1000$$$. Тогда все будет работать за $$$1000\cdot n$$$. При заданных ограничениях задачи, такое решение будет работать меньше 1 сек.

Первое, что я делаю — это рисую массив $$$a$$$, а под ним массив $$$b$$$. Я вижу из условия, что мы меняем местами элементы $$$a_i$$$ и $$$b_i$$$. Влияет ли эта операция на другие элементы?

Нет, не влияет. То есть мне нужно для каждого $$$i$$$ выбрать, какой из двух элементов $$${a_i,b_i}$$$ пойдет в массив $$$a$$$, а какой в массив $$$b$$$. Дальше я смотрю на выражение, которое мне нужно максимизировать и на ограничения задачи. Вижу, что $$$1 \le a_i, b_i$$$ — положительные числа. В выражении есть слагаемое $$$\max(a)$$$, в таком случае мне удобно предположить, что максимум лежит где-нибудь в элементе $$$a_j$$$. Тогда как будет выглядеть выражение?

Выражение будет равно $$$a_j + \sum\limits_{i=1}^{n}b_i$$$. Раз я зафиксировал $$$a_j$$$, то я знаю $$$b_j$$$, а вот остальные $$$b_i, i\neq j$$$ я не знаю. Как мне выбрать остальные элементы $$$b_i$$$?

В качестве остальных элементов мне выгодно выбрать $$$max(a_i, b_i)$$$. Хоршо, тогда мне удобно в начале сделать так, чтобы $$$a_i \le b_i$$$ (с помощью операции из условия). Тогда я могу посчитать заранее $$$S = \sum\limits_{i=1}^{n}\max(a_i, b_i)$$$. Я ее считаю, потому что в будушем мне нужно будет вычислить второе слагаемое в выражении. Теперь, допустим, я считаю, что максимум лежит в $$$j$$$-м элементе. Причем возможно я опять сделаю операцию к $$$j$$$-му элементу. Тогда чему будет равна сумма $$$b$$$?

Она будет равна $$$S' = S - \max(a_i,b_i)+b_i$$$ — здесь я беру предподсчитанную сумму $$$S$$$, убираю $$$\max(a_i,b_i)$$$, потому что это слагаемое было в случае, если я предполагаю, что $$$a_i \le b_i$$$. А дальше добавляю текущий элемент $$$b_j$$$. Хорошо, тогда я могу обновить ответ с помощью числа $$$a_j + S'$$$. Но погодите. А что если $$$a_j$$$ не максимум? Все сломалось?

Нет, ничего не сломалось. Потому что наше выражение $$$a_j + S' \le ANS$$$, где ANS — ответ, потому что $$$a_j \le max(a)$$$. Но с другой стороны, в какой-то момент наш $$$a_j$$$ будет максимумом в оптимальном ответе и мы получим результат. Это частый метод — если мы хотим максимизировать что-то, где есть слагаемое $$$\max(a)$$$, то мы не обязаны делать так, чтобы $$$a_j$$$ был максимумом, а можем просто перебрать все возможные $$$a_i$$$, чтобы получить ответ.

Я очень часто в задачах в голове представляю оптимальный ответ. Как он может выглядеть в этой задаче?

В этой задаче в оптимальном ответе все $$$a_i \lt 0$$$. Могу ли я получить такой ответ?

Точно не знаю, но попробую его получить. Какое простое действие я могу сделать? Я могу взять например самый левый $$$i$$$, что $$$a_i \gt 0$$$ и поменять знак на префиксе, но тогда $$$a_i$$$ станет отрицательным а все элементы левее него станут положительными, нам это не подходит. Что еще могу простого сделать? Какой $$$a_i \gt 0$$$ выбрать?

Могу взять самый правый $$$i$$$, что $$$a_i \gt 0$$$, тогда правее него все элементы $$$a_j \lt 0, j \gt i$$$. Тогда после применения этой операции $$$a_i$$$ станет отрицательным, все элементы левее него поменяют знак, а элементы правее останутся отрицательными. Тогда где будет следующий положительный элемент?

Следующий положительный элемент будет левее $$$i$$$, а именно в некотором индексе $$$k \lt i$$$, потому что мы сделали $$$a_i \lt 0$$$, причем $$$a_j \lt 0$$$ для всех $$$j \gt i$$$. Что мы можем тогда сделать?

Мы можем опять взять самый правый положительный элемент и применить операцию к нему. Тогда в итоге мы получим все $$$a_i \lt 0$$$. Посмотрю на ограничения. $$$n \le 2\cdot 10^5$$$, здесь не зайдет $$$O(n^2)$$$, но зайдет $$$O(n)$$$. Как я буду тогда действиовать?

Раз индекс самого правого положительного элемента у меня уменьшается, то есть двигается влево, то как мне выгодно обходить массив?

Мне выгодно обходить массив справа налево. Но я не могу втупую выполнять операции, потому что в таком случае решение будет работать за $$$O(n^2)$$$. Хорошо, что мне вообще нужно знать?

Мне нужно знать, какой знак у текущего элемента $$$a_i$$$. Что мне для этого нужно?

Раз каждая операция меняет знак на префиксе, то мне нужно знать количство операций, которые я уже сделал. Допутим я сделал $$$C$$$ операци. Какой тогда будет знак у текущего $$$a_i$$$?

Если $$$C$$$ четное, то знак не поменяется, а если нечетное, то поменяется. Тогда я могу определить знак $$$a_i$$$ и если $$$a_i \gt 0$$$, то применить очередную операцию, увеличив $$$C$$$ на единицу.