Дан набор чисел. Надо расставить между ними знаки сложения и вычитания, чтобы получившееся выражение было максимально близко к заданному числу. Количество чисел не больше, чем 10 4 , а сами числа не превосходят 10 4 по модулю. Ограничение по времени: 1 секунда.
Полный перебор не проходит по времени.
Какие есть предложения?
2 ответа 2
Попробуйте такой вариант.
Отсортировать числа по убыванию, после чего последовательно вычитать их из нужного результата. Когда значение станет 0 снова на минус и т.д.
В конце инвертировать операции. То есть поменять все минусы на плюсы и наоборот.
UPD Либо же, чтоб в конце не инвертировать, начать с прибавления к нулю и сходиться вокруг заданного результата
UPD2
result 6265 target 6265 time 0.024444095652956
result 8503 target 8501 time 0.024614095687866
result 4126 target 4125 time 0.024505853652954
result 5147 target 5146 time 0.025776863098145
UPD3 Можно так, но сильно медленней(хотя в секунду укладывается)
Загрузка...
