Переверните минимальные знаки элементов массива, чтобы получить минимальную возможную сумму положительных элементов [зак ⇐ C++

[Anonymous]

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

Я попытался решить проблему, используя жадный подход, но, к сожалению, мои результаты в нескольких тестовых случаях оказались неверными. Вот что я сделал:
[*]Вычисление суммы: сначала я вычислил сумму всех элементов данного массива. [*]Сортировка: Далее я отсортировал массив по возрастанию. [*]Обход массива: При перемещении по отсортированному массиву от самого большого элемента к самому маленькому а. Рассчитал результирующую сумму элементов массива, если знак элемента (где присутствует мой индекс) перевернут. б. Если полученная сумма становилась положительной, я увеличивал счетчик c и обновил сумму как результирующую сумму. в. Если после изменения знака сумма оставалась отрицательной, я не менял знак этого термина. [*]Наконец, я вернул количество элементов, знак которых нужно перевернуть. Вот мой код
#include #include #include использование пространства имен std; интервал основной() { интервал н; цин >> п; вектор arr (n); int sum= 0;//Вычисляет сумму элементов, присутствующих в массиве for (int i = 0; i < n; i++) { cin >> arr; сумма+= arr; } sort(arr.begin(), arr.end()); число интервалов = 0; for (int i = n - 1; i >= 0; i--) { if(sum- 2 * arr == 0){ //sum-2*arr соответствует сумме элементов, присутствующих в массиве, если знак элемента перевернут считать++; сумма-= 2 * arr; перерыв; } иначе, если (сумма 2 * arr > 0) { считать++; сумма-= 2 * arr; } еще { продолжать; } } cout