что творят девелоперы

Spoiler alert тогда уж.

#include <stdio.h>

void skyscrapers(int *heights, int heights_length) {
    int i;
    int current_water = 0;
    int current_height = heights[0];
    int result = 0;
    int last_scraper = 0;
    for (i = 1; i < heights_length; i++) {
        if (heights[i] >= current_height) {
            result += current_water;
            current_water = 0;
            current_height = heights[i];
            last_scraper = i;
        } else {
            current_water += current_height - heights[i];            
        }
    }
    //now we go a different way
    current_height = heights[heights_length - 1];
    current_water = 0;
    for (i = heights_length - 2; i >= last_scraper; i--) {
        if (heights[i] >= current_height) {
            result += current_water;
            current_water = 0;
            current_height = heights[i];
        } else {
            current_water += current_height - heights[i];            
        }
    }
    result += current_water;

    printf("%i", result);
}

Всё, въехал. Кол-во воды от каждого небоскрёба определяется его высотой и высотой его самых высоких соседей. Ну или

volume[i] = min(max(hs[:i], max(hs[i+1:])) - hs[i]

Оказалось так просто, но я убил целый день чтобы это понять. А вот как твой код работает я не понимаю. Можешь объяснить?

Мой исходник целиком:

def getrmaxes(hs):
  """ the highest skyscraper to the right of i-th position """
  i = len(hs)-1
  maxright = hs[i]
  tbl = [0]*len(hs)
  while i:
    maxright = max(maxright, hs[i])
    tbl[i] = maxright
    i -= 1
  return tbl

def skyscrapers(hs):
  volume = 0
  lmax = 0  # the highest skyscraper on the left
  rtbl = getrmaxes(hs)
  rmax = rtbl[-1]  # the highest skyscraper on the right
  i = 1
  while i < len(hs)-1:
    lmax = max(lmax, hs[i-1])
    rmax = rtbl[i+1]
    v = min(lmax,rmax)-hs[i]
    if v>0:
      volume += v
    i += 1
  print(volume)

Не могу проверить сейчас, но разве это решит случай 197667833351? Ответ: 12. Или условие плохо понял?

Да, решает :). Можно решение представить графически. Каждый небоскрёб не может наполниться водой выше краёв. А края в данном случае это небоскрёбы с бокой которые выше данного. Это можно обосновать законом архимеда :).

Если один из края разной высоты то вода будет вытекать пока уровень не сравняется по высоте самого низкого бортика. Поэтому берём min(lmax, rmax).

Вот здесь можно код выполнить из браузера: http://pythontutor.com/

Немного интерфейс запутанный, но разобраться можно. По-дефолту оно выполняет по шагам, так что жми last и снизу будет результат.

Сначала идём по массиву слева направо, вода не может быть выше, чем высота самого высокого на текущий момент из пройденных здания. Текущая высота самого высокого здания у меня в current height, текущий объём воды в current water (что-то мне с утра сейчас кажется, что можно было обойтись без current water, сразу прибавлять к result, но не суть). Доходим до более высокого здания — сбрасывает current water в result, меняем current height.

Таким образом узнаем число воды слева вплоть до самого высокого здания (и номер самого высокого здания в массиве). Идём по массиву справа налево до этого здания, чтобы узнать сколько справа от него воды по такому же принципу.

Код решал на сишке потому что я не сразу заметил выбор языка чтобы не было искушения в цикле вызывать max, min и подобное, которые сами по себе уже O(n).

EDIT: А не, current water нужен чтобы в случаях вроде 11211 отбросить накопившиеся 2 куба воды с правого краю при первом обходе.

не было искушения в цикле вызывать max, min и подобное, которые сами по себе уже O(n).

У меня тоже такого нету :(. min и max вызываются только для двух аргументов. Там где я натравливаю max() на массив это только для примера.

true_admin мой вариант, без max/mix. работает раза в 4 быстрей твоего)

def skyscrapers(heights):
    highest_height = 0
    highest_height_ind = 0
    total_water = 0
    for ind, height in enumerate(heights):
        if height >= highest_height:
            total_water += sum([highest_height - h for h in heights[highest_height_ind:ind]])
            highest_height = height
            highest_height_ind = ind
        elif height > heights[ind - 1]:
            for i, change_height in enumerate(reversed(heights[highest_height_ind:ind])):
                if change_height < height:
                    total_water += height - change_height
                    heights[ind - i - 1] = height
                else:
                    break
    print total_water

Хм, любопытно. Завтра посижу с профайлером, интересно откуда скорость берётся.

Твой вариант в два с половиной раза медленнее моего :P

Ты, случайно, не на тривиальных данных проверял? В исходной задаче на вход поступает 100 тыщ небоскрёбов.

Но всё равно поздравляю с решением, ты побил многих тутошних программистов :)

От я лоханулся( проверял на небольшом массиве в цикле. 100 тыщ небоскребов можно рандомно сгенерить для теста или там какой-то особенный набор данных?

Это конечно утешает) Будут еще интересные задачки, кастуй меня.

Вот данные из их теста: https://cloud.mail.ru/public/484d887d8b90/inpt.py

Хочешь попробовать написать калькулятор? Для простых выражений типа «1 +2 - 3*(4/ 2)». Т.е. целые числа и четыре арифметические операции.

Это одно из заданий.

Спасибо. Поправил свой код, теперь отставание всего в полтора раза. Дальше надо уже полностью менять алгоритм.

Зарегался на talentbuddy. Буду пробовать решать задачки оттуда.

Не. надо с плавающими, и atof, atoi самому реализовать + неограниченное количество выражений, но чтобы не усложнять результат не больше double.

и ещё можно упростить так 1 2 + 3 - 4 2 / *

atof, atoi самому реализовать

atoi тривиально, а вот atof как? У меня пока идея разложить, скажем, 0.123 на 1/10.0 + 2*1/100.0 + 3*/1000.0 ....

и ещё можно упростить так 1 2 + 3 - 4 2 / *

Так задача-то и состоит в том чтобы преобразовать к подобной записи с линейным оператором.