Вода между стен, забавный тест от программистов твиттера Опции

[ilyabvt]

а для { 3, 1, 2, 1, 4, 1, 2, 1, 4 } неправильно считает.

Обновил код, теперь правильно:

Раскрывающийся текст

int calcWaterVolume(int count, int *x)
{
    int result = 0;
    int left, right, middle, level;

    if (count < 3) { return 0; }

    for (left=0;  left<count-1;  ++left) {
        if (x[left+1] < x[left]) { break; }
    }
    for (right=count-1;  right>=1;  --right) {
        if (x[right-1] < x[right]) { break; }
    }

    while (left < right) {
        for (middle=left+1;  middle<right;  ++middle) {
            if (x[middle] >= x[left]) { break; }
        }
        level = std::min(x[left], x[middle]);   //min на случай middle==right
        for (int i=left; i<middle; ++i) {
            if (level-x[i] > 0) { result += level-x[i]; }
        }
        left = middle;
    }

    return result;
}

[Iron Bug]

Iron Bug, а вчера абсолютно внезапно посетил твой город Симпатичный город. Но равнина (это я о ландшафте) непривычная, конечно, для глаза

да уж где тут равнина? почти все улицы вверх или вниз идут уральские горы, однако. конечно, не Кавказ, но и равниной назвать трудно.

[Iron Bug]

Обновил код, теперь правильно:

обновляй ещё:
{ 2, 4, 4, 0, 0, 3, 0, 1, 2 }
я тупо сделала генерацию случайных последовательностей и сравниваю. если результаты разных алгоритмов разные - проверяю вручную.

[Алексей1153]

Iron Bug, наверное, в самом городе из-за зданий не видать. Но на окраинах - поле поле поле, а там лес. Некуда бечь



я ещё алгоритм придумал - пусть некий муравей ползёт через всю стену слева направо. Он запоминает координату (Di), где он начал спускаться вниз. Также он связывает с каждой Di координату Ui, где он шёл вверх и уровень был равен равен или меньше Di. После прохождения всей стены берём все группы D-U и интегрируем пустое место под ними

Можно оптимизировать - группы не собирать, а завершённые интегрировать сразу

Сообщение отредактировал Алексей1153 - 20.5.2014, 6:55

[Алексей1153]

ещё оптимизация для муравья - ему не обязательно спускаться на дно ям, он может их переплывать на глубине 1 блок

[ilyabvt]

Обновил код, теперь правильно:

обновляй ещё:
{ 2, 4, 4, 0, 0, 3, 0, 1, 2 }
я тупо сделала генерацию случайных последовательностей и сравниваю. если результаты разных алгоритмов разные - проверяю вручную.

Обновил еще
На этот раз тоже проверял на случайных последовательностях.

Раскрывающийся текст

int calcWaterVolume(int count, int *x)
{
    int result = 0;
    int left, right, middle, level;

    if (count < 3) { return 0; }

    for (left=0;  left<count-1;  ++left) {
        if (x[left+1] < x[left]) { break; }
    }
    for (right=count-1;  right>=1;  --right) {
        if (x[right-1] < x[right]) { break; }
    }

    while (left < right) {
        for (middle=left+1;  middle < right;  ++middle) {
            if (x[middle] > x[middle-1]  &&  x[middle+1] <= x[middle]) {
                bool needbreakCycle = true;
                for (int i=middle+1; i<=right; ++i) {
                    if (x[i] > x[middle]  &&  x[middle] <= x[left]) {
                        middle = i-1;       //-1 т.к. на каждой итерации ++middle
                        needbreakCycle = false;
                        break;
                    }
                }
                if (needbreakCycle) { break; }
            }
        }
        level = std::min(x[left], x[middle]);   //min на случай middle==right
        for (int i=left; i<middle; ++i) {
            if (level-x[i] > 0) { result += level-x[i]; }
        }
        left = middle;
    }

    return result;
}