Создайте массив с K положительными числами, так что arr[i] равен -1 или 1, а сумма массива положительна.

Опубликовано: 22 Сентября, 2022

Даны два положительных целых числа, N и K ( 1 ≤ K ≤ N ), задача состоит в том, чтобы построить массив arr[] ( индексирование на основе 1 ) таким образом, чтобы каждый элемент массива arr[i] был либо i , либо -i , а массив содержит ровно K положительных значений, таких что сумма элементов массива положительна. Если таких последовательностей можно сгенерировать несколько, выведите любую из них. В противном случае выведите «-1» .

Примеры:

Input: N = 10, K = 6
Output: -1 2 -3 4 -5 6 -7 8 9 10
Explanation:
Consider the sequence as {-1, 2, -3, 4, -5, 6, -7, 8, 9, 10}, the sum of the constructed sequence is (-1) + 2 + (-3) + 4 + (-5) + 6 + (-7) + 8 + 9 + 10 = 23, which is positive.

Input: N = 7, K = 2
Output: -1

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

  • Инициализируйте массив, скажем, arr[] , в котором хранится результирующая последовательность.
  • Инициализируйте две переменные, скажем, sumNeg и sumPos как 0 , чтобы сохранить сумму первого (N – K) и оставшихся элементов соответственно.
  • Переберите диапазон [0, N – K – 1] , используя переменную i , обновите значение arr[i] до -(i + 1) и добавьте значение arr[i] к переменной sumNeg .
  • Переберите диапазон [N – K, N – 1], используя переменную i , обновите значение arr[i] до (i + 1) и добавьте значение arr[i] к переменной sumPos .
  • Если значение абсолютного значения sumNeg больше, чем sumPos , то выведите -1 . В противном случае в качестве результата выведите элементы суммы в массиве arr[].

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N)
Вспомогательное пространство: O(N)

РЕКОМЕНДУЕМЫЕ СТАТЬИ