alexbuki
@alexbuki
программист js

Что нужно сделать в задаче? Что значит выпирающие точки?

Задача с контеста Яндекса:

Писать свой игровой движок с нуля всегда сложно. Но не для Васи! Он потратил уже много времени, чтобы описать графику и физику.
Одна из задач — уменьшение суммы по точкам. Код был написан давно, и Вася не помнит, зачем он вообще был нужен. А если его удалить, то движок совсем перестаёт работать.
Представим, что даётся некоторая последовательность точек и количество операций. Помогите Васе — напишите функцию, которая будет схлопывать массив.
Делать это представляется следующим образом: нужно выпирающие точки обратить (умножить на –1) таким образом, чтобы сумма была минимальной. Выпирающие области обращать можно несколько раз. По минимальной сумме движок будет определять порядок отрисовки.
Раньше разработчик придумал гениальное решение. Всё работает прекрасно. Но, к сожалению, тормозит. Помогите ему решение, которое будет работать быстрее. Текущее решение представлено ниже.

/**  
 * A {number[]} - массив целых чисел  
 * K {number} - количество операций  
 */  
module.exports = function solve ({ A, K }) {  
    if (K === 0) return A.reduce((a, b) => a + b, 0);  
 
    const r = Math.min(...A.map((el, index) => {  
        const a = [...A];  
        a[index] = -el;  
        return solve({ A: a, K: K - 1 });  
    }));  
 
    return r;  
};

Примеры
solve({ A: [ 167, -4893, -3864, 5597 ], K: 2, }); // -14521

solve({ A: [ 2943, -5014, -7766, -5408 ], K: 2, }); // -15245
Формат ввода
На вход подаётся 2 аргумента:

points — массив точек x. Значения внутри него всегда определены и лежат в промежутке -100000 и 100000
operations — максимальное количество обращений x. Всегда выражено числом и лежит в промежутке 1 и 1000000

Я сделал так, но решение не проходит все тесты:
function solve ({ A, K }) {
  A.sort((a, b) => b - a)
  for (let i = 0; i < K; i++) {
    if (A[i] > 0) { A[i] = A[i] * -1 }
  }
  return A.reduce((a, b) => a + b, 0)
}


Не понимаю что значит выпирающие точки, мин и макс?
  • Вопрос задан
  • 98 просмотров
Пригласить эксперта
Ответы на вопрос 1
alexbuki
@alexbuki Автор вопроса
программист js
Решение, которое прошло все тесты:
function solve ({ A, K }) {  
    if (K === 0) return A.reduce((a, b) => a + b, 0);  
    A.sort((a,b) => b - a)
    for (i =0; K > 0; i++, K--) {
        if (A[i] > 0) {
            A[i] = -A[i]
        } else {
            break
        }
    }
    A.sort((a,b) => b - a)
    if (K%2 === 1) {
        A[0] = -A[0]
    }
    return A.reduce((a, b) => a + b, 0)
}
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы