Строковый парсинг прогресса в C

Да, вы можете спасти ваше решение, добавив дополнительный for -кольцо.

Что вам нужно сделать, так это то, что если вы обнаружите, что ваша предыдущая пара ботинок может привести вас к плитке, которая слишком глубоко в снегу для вашей следующей пары, то вам нужно попытаться «вернуться» к последней плитке. это не слишком глубоко. В итоге получается решение в худшем случае O ( N · B ) времени и O (1) дополнительного пространства. [ 1161]

Может быть не очевидно, почему можно возвращаться к этой плитке - в конце концов, только потому, что вы можете достичь данной плитки, это не обязательно означает, что вы смогли добраться до всех плиток до нее - поэтому позвольте мне объясните немного, почему это нормально хорошо.

Пусть maxReachableTileNum будет номером (от 1 до N ) последней плитки, которой вы смогли достичь с вашими предыдущими ботинками, и пусть lastTileNumThatsNotTooDeep будет числом (от 1 до [ 1130] N ) последней плитки на или перед maxReachableTileNum, которая не слишком покрыта снегом для вашей следующей пары. (Мы знаем, что есть такая плитка, потому что плитка # 1 вообще не имеет снега, поэтому, если ничего другого, мы не знаем, что мы можем вернуться к самому началу.) Теперь, так как мы смогли получить до maxReachableTileNum, затем некоторая предыдущая загрузка должна была либо наступить на lastTileNumThatsNotTooDeep (в этом случае нет проблем, она достижима), либо пропустить его до некоторой более поздней плитки (до или после maxReachableTileNum) , Но эта более поздняя плитка должна быть глубже, чем lastTileNumThatsNotTooDeep (потому что эта более поздняя плитка больше, чем с _{currentBootNum} , что, по крайней мере, не меньше глубины lastTileNumThatsNotTooDeep ), что означает, что ботинок, который пропустил lastTileNumThatsNotTooDeep, безусловно, мог бы наступить на lastTileNumThatsNotTooDeep вместо этого: это означало бы сделать более короткий шаг (ОК) на плитку с менее глубоким покрытием (ОК ) чем то, что он на самом деле сделал. Так или иначе, мы знаем, что lastTileNumThatsNotTooDeep было достижимо. Поэтому мы можем попытаться вернуться к lastTileNumThatsNotTooDeep. (Примечание: приведенный ниже код использует имя reachableTileNum вместо lastTileNumThatsNotTooDeep, потому что он продолжает использовать переменную reachableTileNum для поиска вперед, чтобы найти достижимые тайлы.)

Однако нам все еще нужно удерживать на предыдущий maxReachableTileNum: возврат может оказаться бесполезным (потому что он может не позволить нам продвинуться вперед дальше, чем у нас уже есть), в этом случае мы просто откажемся от этих ботинок и перейдем к следующему пара, с maxReachableTileNum в его предыдущем значении.

Итак, в целом, мы имеем это:

public static int solve(
    final int[] tileSnowDepths,           // tileSnowDepths[0] is f_1
    final int[] bootAllowedDepths,        // bootAllowedDepths[0] is s_1
    final int[] bootAllowedTilesPerStep   // bootAllowedTilesPerStep[0] is d_1
) {
    final int numTiles = tileSnowDepths.length;
    final int numBoots = bootAllowedDepths.length;
    assert numBoots == bootAllowedTilesPerStep.length;

    int maxReachableTileNum = 1; // can reach tile #1 even without boots

    for (int bootNum = 1; bootNum <= numBoots; ++bootNum) {
        final int allowedDepth = bootAllowedDepths[bootNum-1];
        final int allowedTilesPerStep = bootAllowedTilesPerStep[bootNum-1];

        // Find the starting-point for this boot -- ideally the last tile
        // reachable so far, but may need to "backtrack" if that tile is too
        // deep; see explanation above of why it's safe to assume that we
        // can backtrack to the latest not-too-deep tile:

        int reachableTileNum = maxReachableTileNum;
        while (tileSnowDepths[reachableTileNum-1] > allowedDepth) {
            --reachableTileNum;
        }

        // Now see how far we can go, updating both maxReachableTileNum and
        // reachableTileNum when we successfully reach new tiles:

        for (int tileNumToTry = maxReachableTileNum + 1;
             tileNumToTry <= numTiles
                 && tileNumToTry <= reachableTileNum + allowedTilesPerStep;
             ++tileNumToTry
        ) {
            if (tileSnowDepths[tileNumToTry-1] <= allowedDepth) {
                maxReachableTileNum = reachableTileNum = tileNumToTry;
            }
        }

        // If we've made it to the last tile, then yay, we're done:

        if (maxReachableTileNum == numTiles) {
            return bootNum - 1; // had to discard this many boots to get here
        }
    }

    throw new IllegalArgumentException("Couldn't reach last tile with any boot");
}

(я проверил это на примере данных USACO, и он вернул 2, как и ожидалось.)

Это может быть оптимизированы далее, например с логикой, чтобы пропустить пары загрузок, которые явно не полезны (потому что они не более сильные и не более гибкие, чем предыдущая успешная пара), или с дополнительной структурой данных, чтобы отслеживать позиции последних минимумов (чтобы оптимизировать возврат) процесс), или с логикой, чтобы избежать возврата назад дальше, чем это возможно; но учитывая, что N · B & nbsp; ≤ & nbsp; 250 ^{2 sup> = & nbsp; = & nbsp; 62,500, я не думаю, что такая оптимизация оправдана. [1 167]}

Отредактировано, чтобы добавить (2019-02-23): я подумал об этом дальше, и мне пришло в голову, что на самом деле можно написать решение в худшем случае [1137 ] O ( N + nbsp; B log N ) времени (которое асимптотически лучше, чем O ] ( N · B )) и O ( N ) дополнительное пространство. Но это намного сложнее; он включает в себя три дополнительные структуры данных (одну для отслеживания позиций последних минимумов, чтобы обеспечить возможность обратного отслеживания за O (log & nbsp; N ) время; одну для отслеживания позиций из будущих минимумов, чтобы разрешить проверку за O (log & nbsp; N ), если откат на самом деле полезен (и если да, то двигаться вперед к соответствующему минимуму ) и один для поддержания необходимой прогнозной информации, чтобы второй был сохранен в амортизированном O (1) времени). Также сложно объяснить, почему это решение гарантированно находится в пределах O ( N + B & nbsp; log & nbsp; N ]) время (потому что оно включает в себя много амортизированного анализа , и внесение незначительного изменения, которое может показаться оптимизацией - например, замена линейного поиска на бинарный поиск - может нарушить анализ и фактически ] увеличивают сложность времени в наихудшем случае. Поскольку N и B оба, как известно, составляют не более 250, я не думаю, что все осложнения того стоят. [ 1168]