Вода между стен, забавный тест от программистов твиттера Опции Подписка на тему Сообщить другу Версия для печати Скачать тему Подписка на этот форум Режимы отображения Древовидный Переключить на: Стандартный Переключить на: Линейный

[Iron Bug]

Попалась тут забавная задачка
Задача:
http://qandwhat.apps.runkite.com/i-failed-...tter-interview/
Дя тех, кто не очень хорошо понимает по-английски, задача вкратце:
Представлен последовательный набор чисел. Числа указывают "высоту стен", стоящих рядом. Задача: посчитать количество воды, которая может накопиться в таком резервуаре, если пройдёт дождь. Вода через низкие препятствия утекает, как и полагается воде. С краёв она тоже утекает.

[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;
}