Как максимизировать сумму?

Нам дан отсортированный массив.

Пусть начальное значение pass равно нулю.

Мы можем выполнить следующую операцию любое количество раз:

  1. Выберите любые k номера за раз. Добавьте их все. Добавьте эту сумму к pass

  2. Если число, например x, выбирается в первый раз из массива, то оно считается только x. Когда он выбран второй раз, то он считается как -x, а в третий раз снова как x и так далее...

Например, пусть массив будет [-14, 10, 6, -6, -10, -10, -14] и k = 4, и мы проделаем операцию только один раз. Выбираем эти 4 числа: {14, 10, 6, -6}. Складывая их, мы получаем 24. Затем pass=pass+24. Следовательно, максимальное значение прохода равно 24.

Как получить максимальное значение pass?


arrays sorting algorithm implementation
person sdrtg ghytui    schedule 10.06.2019    source источник
comment
Вопросы типа домашних заданий см. в этом руководстве о том, как их задавать. В частности, предоставьте информацию о том, что вы уже пробовали, и предоставьте MCVE.   -  person Das_Geek    schedule 10.06.2019
comment
Мой второй пункт остается в силе   -  person Das_Geek    schedule 10.06.2019
comment
Если нет ограничений на количество операций, максимальная сумма может быть получена после бесконечных сложений.   -  person nice_dev    schedule 10.06.2019
comment
Нет. Ваша логика неверна. Достаточно будет конечного числа ходов.   -  person sdrtg ghytui    schedule 10.06.2019
comment
@Firexsecred Звучит так, как будто у вас уже есть решение. Так ли это?   -  person Nico Schertler    schedule 10.06.2019
comment
Да, у меня есть. Я здесь, чтобы подтвердить, прав ли я. Это действительно простая проблема.   -  person sdrtg ghytui    schedule 10.06.2019
comment
@Firexsecred Можете ли вы уточнить, как конечное количество ходов всегда дает вам максимальную сумму?   -  person nice_dev    schedule 10.06.2019
comment
Скажем, вы выбираете «2», добавляете его. Теперь, когда вы снова выбираете 2, это -2; теперь 2-2=0; теперь, делая это бесконечное количество раз, мы получим ноль или 2, мы пойдем с +2 :-)   -  person sdrtg ghytui    schedule 10.06.2019
comment
Вы можете выбрать разные окна k.   -  person nice_dev    schedule 10.06.2019
comment
см. ответ и объяснение в комментариях к ответу :-)   -  person sdrtg ghytui    schedule 11.06.2019
comment
@גלעדברקן Я решил эту проблему, спасибо, что заглянули. На самом деле, я создал эту задачу, потому что хотел добавить ее в будущем конкурсе :-)   -  person sdrtg ghytui    schedule 11.06.2019
comment
@Firexsecred Я обнаружил, что вы приняли ответ, который во многих случаях неверен. Было бы неплохо, если бы вы дали хороший ответ на этот ваш вопрос. Либо бесполезно размещать информацию на этом сайте.   -  person Resorcinol    schedule 11.06.2019
comment
@Resorcinol Нет, этот ответ на 100% правильный, можете ли вы показать мне случай, когда что-то пойдет не так, за исключением случаев, когда k = n?   -  person sdrtg ghytui    schedule 11.06.2019
comment
@Firexsecred Для 4 4 2 -1 -1 -3 и k = 5? Какой ответ? Это не 10. Это покажите мне, как?   -  person Resorcinol    schedule 11.06.2019
comment
Ответ только 10 :-) Я пишу объяснение в следующем комментарии :-)   -  person sdrtg ghytui    schedule 11.06.2019
comment
Ответ только 10 :-) Я пишу объяснение в следующем комментарии :-)   -  person sdrtg ghytui    schedule 11.06.2019
comment
Мы выбираем: {4,4,2,-1,-3}......эти 5 чисел.....сумма 6, следовательно, pass=6 ; соглашаться ? затем: ---›новый массив выглядит следующим образом: --›{-4,-4,-2,-1,1,3}....теперь выберите:-{-4,-4,-2, -1,1}.....сумма=-10; теперь пройти=6-10=-4; теперь..... новый массив выглядит так:-{4,4,2,1,-1,3}.....выберите:-{4,4,2,1,3}=== ›сумма===›14; поэтому pass=14-4=10 :-) Надеюсь теперь все понятно! :-)   -  person sdrtg ghytui    schedule 11.06.2019
comment
@Firexsecred Действительно хороший вопрос, хорошо сформулированный. Но как бы вы интерпретировали нули в своем массиве?   -  person Resorcinol    schedule 11.06.2019
comment
Считайте нули положительными числами в вашем коде :-)   -  person sdrtg ghytui    schedule 11.06.2019
comment
Вы можете посмотреть на: codechef.com/AVEN2019/problems/AVN002   -  person Ganesh Jadhav    schedule 11.06.2019

Ответы (1)


arrow_upward
4
arrow_downward

Мы можем переформулировать задачу следующим образом:

У нас есть список номеров, и мы можем активировать или деактивировать номера. Мы хотим найти максимальную сумму активированных номеров, при которой за каждый проход мы можем поменять местами ровно k номеров.

Для нечетного k мы могли бы сделать следующее: активировать максимальное число (если оно положительное) и использовать оставшиеся переключатели (k-1) для переключения любого числа дважды, что эффективно оставит число в его предыдущем состоянии. Следовательно, максимальное значение pass представляет собой сумму положительных чисел.

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

Изменить из комментариев:

Для особого случая, когда k=n, есть только два варианта: включить все числа или исключить все числа. Если сумма чисел больше 0, это результат. В противном случае результат равен 0.

person Nico Schertler    schedule 10.06.2019
comment
Комментарии не для расширенного обсуждения; этот разговор был перемещен в чат< /а>. - person Samuel Liew♦; 12.06.2019