Я пытаюсь решить эту проблему, которую я опубликовал ранее: 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 — размер входного массива. Я ищу лучший подход, который требует меньше времени.
@maraca, check first day of sprints but calculate the score falsely for the last spring unless it is finished on the last day
Я не поняла, не могли бы вы объяснить подробнее?
Внешний цикл находится непосредственно над спринтами, но он должен охватывать дни каждого спринта. Внутренний цикл корректен только для завершенных спринтов, потому что вы начинаете с добавления очков за последний день спринта, а затем идете назад вместо первого дня спринта (т. е. x-й день спринта с правильными внешними циклами) и идете вперед. .
One choice is to start on the last day
потому что в этом случае я начинаю с последнего дня спринта. `вместо первого дня спринта и вперед` Если я сделаю это, я получу неправильный результат.
Получение правильного вывода для некоторых входных данных не означает, что решение правильное. Я понимаю, почему вы это делаете, но это все равно неправильно.
Сначала переберите массив и вычислите 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
При грубом подходе требуется O(sum(arr) * k), вы проверяете только первый день спринта, но ошибочно рассчитываете счет за последнюю весну, если он не завершен в последний день. С помощью скользящего окна вы можете получить O(sum(arr)) независимо от k.