Учитывая массив положительных чисел размера n, выберите как можно больше элементов из этого массива и умножьте на -1, так чтобы совокупная сумма всегда была больше 0. Возвращает количество элементов, которые можно сделать отрицательными в результате.
Пример:
Тестовый пример 1: [5,3,1,2]
Результат = 2
Объяснение:
выберите индексы 1 и 2 и сделайте их отрицательными итак [5,-3,-1,2] совокупная сумма равна [5,2,1,3]
Есть и другие возможности, например
[5,-3,1,-2]
Мой подход к кодированию такой:
static int solve(int[] arr) {
long sum = 0;
int result = 0;
for(int e : arr) {
int neg = -e;
if (sum + neg >0) {
result++;
sum += neg;
} else {
sum += e;
}
}
return result;
}
Но мой подход неверен, поскольку в некоторых случаях он дает неверный результат, например:
arr = [5,2,3,5,2,3]
Expected output = 3, my code results = 2
possible solution is [5,-2,3,5,-2,-3]
Каков правильный подход к решению этой проблемы?
@OldDogProgrammer, у меня нет ссылки на эту проблему
Я заметил, что многие ваши вопросы связаны с LeetCode
и другими проблемами, например проблемами. Не хочу отговаривать вас от публикации сообщений на SO, но знаете ли вы, что существует обмен мнениями, посвященный этому типу программирования. Называется он Код Гольф. Подумал, что тебе это может понравиться.
@WJS Соревновательное программирование и код-гольф — это не одно и то же. Очень редко методы решения пересекаются. Эффективность обычно полностью игнорируется при решении задач по кодированию гольфа.
@Unmitigated Ну, когда я прочитал некоторые задачи на Code Golf, они наверняка напоминали многие, которые я видел на сайтах соревновательного программирования.
@WJS Я не хотел подразумевать иное, но проблемы с кодовым гольфом часто решаются грубой силой, поскольку правила требуют только решений для теоретического решения проблемы в конечном итоге. Вопросы по алгоритмам лучше задавать здесь.
Спасибо за ответ. Поскольку для этих задач нам недоступны страницы, для решения будущих проблем может оказаться полезным, если вы поделитесь ограничениями и ожиданиями.
Вы всегда можете попытаться инвертировать текущий элемент, если это возможно, отслеживая при этом элементы, удаленные на данный момент в очереди мультимножества или приоритетной очереди. Если текущий элемент невозможно удалить из суммы, попробуйте заменить его наибольшим ранее удаленным элементом, если последний больше.
static int solve(int[] arr) {
long sum = 0;
int result = 0;
var removed = new PriorityQueue<Integer>(Collections.reverseOrder());
for (int x : arr) {
if (sum - x > 0) {
sum -= x;
removed.add(x);
++result;
} else if (!removed.isEmpty() && removed.peek() > x) {
sum += removed.poll() - x;
removed.add(x);
} else sum += x;
}
return result;
}
Спасибо, я пытаюсь это понять. sum += removed.lastKey() - x;
здесь мы все еще уменьшаем на x правильно, тогда removed.merge(x, -1, Integer::sum)
почему мы уменьшаем его частоту на карте, а не увеличиваем ее.
@learner Это опечатка. Я исправил метод.
Прав ли я, полагая, что временная сложность этого алгоритма составляет O(N log N)? Я думал о попытке грубого решения, которое было бы экспоненциальным.
@ k314159 k314159 Да, это O(N log N).
Есть ли у этой проблемы веб-страница? Если да, то было бы вежливо добавить ссылку.