python - алгоритм суммы префиксов

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

Теперь решение в ссылке, которую вы предоставили, более подробно описывает оптимальную стратегию, идущую по пути таким образом, чтобы человек менял направление только один раз. Таким образом, можно покрыть диапазон левой и правой конечными точками, которые, по-видимому, представляют left_pos и right_pos.

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

Например, в первом цикле вместо того, чтобы выяснять, что представляет собой этот диапазон, попробуйте понять, как на left_pos влияют разные значения, получаемые p. Немного подумав, можно заметить, что left_pos изменяется в соответствии с возможными левыми конечными точками.

В частности, когда p == 0, левая конечная точка является начальным индексом (т.е. k), а когда p равно min(m, k), то это либо 0 (т.е. если k < m), либо (k - m). В первом случае это максимальное расстояние, которое может пройти левая конечная точка, так как она вышла бы за допустимый диапазон точек на дороге. В последнем случае количество ходов запрещает любое решение с left_pos меньшим, чем (k - m), поскольку невозможно перейти от k к этим индексам за m ходов.

Аналогично можно объяснить присвоение right_pos в первом цикле. min включает (n-1), который является самым правым допустимым индексом, который может быть достигнут, и он служит для удержания правильной конечной точки в допустимых пределах. Внутренний оператор max содержит k, так как это наименьшее возможное значение для right_pos. (то есть из-за того, что k является отправной точкой) У него также есть выражение (k + m - 2 * p). Это выражение представляет следующий процесс:

• Идите налево на p ходов.
• Измените направление и идите вправо на p ходов, чтобы добраться до начальной точки.
• Идите направо с оставшимися (m - 2p) ходами.

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

Что касается вашего второго вопроса, я не думаю, что обычной практикой является сдвиг индексов для массивов сумм префиксов. Я обычно использую этот метод в онлайн-соревнованиях по программированию, и моя реализация массива сумм префиксов, который вы используете в Python, будет следующей.

def prefix_sums(A):
    n = len(A)
    P = [0] * n
    P[0] = A[0]
    for k in xrange(1, n):
        P[k] = P[k - 1] + A[k]
    return P

def count_total(P, x, y):
    return (P[y] - P[x - 1] if x > 0 else P[y])

Фундаментальная идея вышеприведенной реализации заключается в том, что в P[x] у нас есть сумма A[0] + A[1] + ... + A[x].

После прочтения темы все еще было трудно понять идею, пока я не реализовал наивное решение (которое находится первым в кодовый документ)

Трудное для понимания решение № 2 просто имитирует движение влево и вправо и все эти странно выглядящие вычисления только для получения левого и правого пределов области (так как вы действительно перемещаетесь внутри нее). Таким образом, каждая итерация означает один полный цикл с использованием 6 шагов.

Если вы двигаетесь влево, а затем вправо (p=0...M), у вас есть

• 0 шагов влево, 6 шагов вправо (на самом деле 0 и 2 шага вызывают выход за границу массива), поэтому левая граница области находится в индексе 4, а правая граница - в индексе 6.
• 1 шаг влево, 5 шагов вправо (на самом деле 1 и 3), поэтому левая граница находится в индексе 3, а правая граница - в индексе 6.
• 2 шага влево, 4 шага вправо(на самом деле 2 и 4)...продолжаем расчеты

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

function prefix_sums(array $a)
{
    $n = count($a);
    $p = array_fill(0, $n + 1, 0);
    for ($i = 1; $i <= $n; $i++) {
        $p[$i] = $p[$i - 1] + $a[$i - 1];
    }
    return $p;
}

function count_total($p, $x, $y)
{
    return $p[$y + 1] - $p[$x];
}

function mushrooms(array $a, int $k, int $m)
{
    $n = count($a) - 1;
    $max = 0;
    $sums = prefix_sums($a);
    //start  moving to the left and then the right
    for ($p = 0; $p < $m; $p++) {
        $stepsLeft = $p;
        $realStepsLeft = min($k, $stepsLeft);
        $leftBorder = $k - $realStepsLeft;

        $stepsRight = $m - $stepsLeft;
        $realStepsRight = min($n - $leftBorder, $stepsRight);
        $rightBorder = $leftBorder + $realStepsRight;

        $max = max($max, count_total($sums, $leftBorder, $rightBorder));
    }
    //moving to the right and then the left
    for ($p = 0; $p < $m; $p++) {
        $stepsRight = $p;
        $realStepsRight = min($p, $n - $k);
        $rightBorder = $k + $realStepsRight;

        $stepsLeft = $m - $stepsRight;
        $realStepsLeft = min(($k + $realStepsRight), $stepsLeft);
        $leftBorder = $rightBorder - $realStepsLeft;

        $max = max($max, count_total($sums, $leftBorder, $rightBorder));
    }
    return $max;
}

assert(ASSERT_EXCEPTION, 1);
assert(mushrooms([2, 3, 7, 5, 1, 3, 9], 4, 6) == 25);

echo 'Success';