Логика, которую нужно реализовать, чтобы получить максимальное количество очков

Я пытаюсь решить эту проблему, которую я опубликовал ранее: https://stackoverflow.com/questions/78270434/calculate-maximum-points-earned/78270606

Пример. Имеется n = 3 спринта, количество дней каждого спринта —days = [2,3,2] и k=4.

Максимальное количество очков, которое можно набрать = 2+1+2+3 = 8.

Один из вариантов — начать в последний день первого спринта и закончить в последний день второго спринта.

Вот мой метод грубой силы, который проверяет каждый индекс, когда он начинает набирать максимальное количество баллов.

static long solve(int[] arr, int k) {
    long maxPoints = 0;
        int n = arr.length;
        for (int i  = 0; i < n; i++) {
            int index = i;
            long currentPoints = 0;
            int k1 = k;
            while (k1 > 0) {
                for (int j = arr[index]; j > 0 && k1 > 0; j--, k1--) {
                    currentPoints += j;
                }
                index++;
                if (index == n) {
                    index = 0;
                }
            }
            maxPoints = Math.max(maxPoints, currentPoints);
        }
        return maxPoints;
}

Этот код выполняется с временной сложностью O(n * k), где n — размер входного массива. Я ищу лучший подход, который требует меньше времени.

При грубом подходе требуется O(sum(arr) * k), вы проверяете только первый день спринта, но ошибочно рассчитываете счет за последнюю весну, если он не завершен в последний день. С помощью скользящего окна вы можете получить O(sum(arr)) независимо от k.

maraca 08.04.2024 03:35

@maraca, check first day of sprints but calculate the score falsely for the last spring unless it is finished on the last day Я не поняла, не могли бы вы объяснить подробнее?

CodeCrusader 08.04.2024 08:32

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

maraca 08.04.2024 10:41
One choice is to start on the last day потому что в этом случае я начинаю с последнего дня спринта. `вместо первого дня спринта и вперед` Если я сделаю это, я получу неправильный результат.
CodeCrusader 08.04.2024 10:53

Получение правильного вывода для некоторых входных данных не означает, что решение правильное. Я понимаю, почему вы это делаете, но это все равно неправильно.

maraca 08.04.2024 10:55
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
Как вычислять биты и понимать побитовые операторы в Java - объяснение с примерами
Как вычислять биты и понимать побитовые операторы в Java - объяснение с примерами
В компьютерном программировании биты играют важнейшую роль в представлении и манипулировании данными на двоичном уровне. Побитовые операции...
Поднятие тревоги для долго выполняющихся методов в Spring Boot
Поднятие тревоги для долго выполняющихся методов в Spring Boot
Приходилось ли вам сталкиваться с требованиями, в которых вас могли попросить поднять тревогу или выдать ошибку, когда метод Java занимает больше...
Полный курс Java для разработчиков веб-сайтов и приложений
Полный курс Java для разработчиков веб-сайтов и приложений
Получите сертификат Java Web и Application Developer, используя наш курс.
0
5
634
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Сначала переберите массив и вычислите sum и score, оценка равна сумме arr[i] * (arr[i] + 1) / 2. Затем вы устанавливаете оценку total на k / sum * score (целое деление) и k = k % sum. k теперь находится в диапазоне от 0 до суммы - 1, это упрощает задачу и важно, чтобы k было намного больше, чем sum. В конце концов вы возвращаете total + bestScore, а bestScore – это скользящее окно с лучшим результатом размером k (новый k, если оно равно 0, вы можете сразу вернуть total).

После этой нормализации вы можете просматривать массив, используя скользящее окно. Простой подход предполагает использование O(sum(arr)), что все равно лучше, чем грубый метод O(k*sum(arr)), но не впечатляет. Ключевым моментом является понимание того, что до тех пор, пока начало и конец окна не меняют спринт, оценка продолжает меняться с постоянной скоростью (это потому, что оценка дня, выпадающего из окна, всегда увеличивается на 1, пока поскольку мы находимся в одном и том же спринте, и то же самое верно для дня, входящего в окно), поэтому мы можем перейти непосредственно к концу более раннего завершившегося спринта и перемещать скользящее окно большими шагами, чем просто один день за раз. Скорость изменения - это разница между днями границ окна, добавьте ее столько раз к текущему счету, сколько дней вперед, затем сравните с лучшим и повторяйте, пока начало окна не достигнет конца массива (конец окна обтекает).

Это приводит к решению O(n), независимому от k, с объемом памяти O(1).

public static long sumUp(int n) {
    return n * (n + 1L) / 2L;
}

public static long solve(int[] arr, int k) {
    // ***** normalize *****
    long sum = 0, score = 0;
    for (int a : arr) {
        sum += a;
        score += sumUp(a);
    }
    long baseScore = k / sum * score;
    k = (int) (k % sum);
    if (k == 0) return baseScore;
    // ***** prepare sliding window *****
    int startSprint = 0, startDay = 0, endSprint = 0, endDay = 0;
    long currScore = 0;
    while (k >= arr[endSprint]) {
        currScore += sumUp(arr[endSprint]);
        k -= arr[endSprint++];
    }
    currScore += sumUp(k);
    endDay = k; // exclusive
    long bestScore = currScore;
    // ***** slide the window *****
    while (startSprint < arr.length) {
        int startDaysLeft = arr[startSprint] - startDay;
        int endDaysLeft = arr[endSprint] - endDay;
        int change = endDay - startDay;
        if (startDaysLeft == endDaysLeft) {
            currScore += change * startDaysLeft;
            startDay = 0;
            endDay = 0;
            startSprint++;
            endSprint = (endSprint + 1) % arr.length;
        } else if (startDaysLeft < endDaysLeft) {
            currScore += change * startDaysLeft;
            startDay = 0;
            endDay += startDaysLeft;
            startSprint++;
        } else {
            currScore += change * endDaysLeft;
            startDay += endDaysLeft;
            endDay = 0;
            endSprint = (endSprint + 1) % arr.length;
        }
        if (currScore > bestScore) bestScore = currScore;
    }
    return baseScore + bestScore;
}

k = k % сумма; не могу преобразовать long в int

soulmachine 22.06.2024 21:08

Другие вопросы по теме

Что происходит с потерянной частью односвязного списка, когда я добавляю цикл в середине?
Эффективный способ найти сумму наибольших элементов x в подмассиве
Инициализируйте двумерный массив значениями, указанными в таблице ниже
Как я могу придумать алгоритм для разделения ряда чисел в заданном соотношении, чтобы округленные разделения складывались в исходное число?
Рекурсивное построение древовидной структуры данных из массива строк, сохраняющих порядок приоритета
Алгоритм разделения целого числа на группы определенных меньших целых чисел
Изменение масштаба массива в JavaScript или Python до определенного максимального значения и целевой суммы
Реализация визуализации дерева жизни в JavaFX с определением клады и иерархии
JS Структура/алгоритм данных для случайного выбора из набора с уменьшением вероятности
Найдите m-й по величине элемент

Похожие вопросы

Невозможно установить артефакт Maven, хотя он, кажется, указан в репозитории Maven
Задача требует сортировки строки, состоящей из строчных и прописных букв
Почему вызывается пользовательский прослушиватель, когда я не подключаю его к TestClass ни через аннотацию, ни через XML-файл пакета? (ТестНГ)
Почему вызов метода take() Java DelayQueue не блокирует всю структуру данных для всех потоков?
Это фабричный паттерн или паттерн стратегии?
Что происходит с потерянной частью односвязного списка, когда я добавляю цикл в середине?
Можно ли заставить picocli не перезаписывать значение, установленное в конструкторе, если в cli нет опции?
Spring MVC: нет конвертера для [класса com.gcu.model.OrderList] с предустановленным типом контента «null»
Как создать фрагментированный файл MPEG-4 (FMP4) из .mp4 на Android с помощью Kotlin или Java (без использования FFmpeg)
Как (де-)сериализация объектов Java работает с универсальными классами?