1

Дана последовательность N прямоугольников различной ширины и высоты (wi,hi). Прямоугольники расположены, начиная с точки (0,0), вправо на оси OX вплотную друг за другом. Требуется найти M — площадь максимального прямоугольника (параллельного осям координат), который можно вырезать из этой фигуры.

Формат входных данных

В первой строке задано число N (1≤N≤105). Далее идут N строк. В каждой строке содержатся два числа: ширина и высота i-го прямоугольника (1<wi≤3⋅104, 0≤hi≤3⋅104).

Формат выходных данных

Выведите искомое число M.

Примеры Ввод
Вывод
3
4 3
2 1
2 5
12
3
4 3
2 1
3 5
15
Ограничения Время выполнения: 5 секунд Помогите, пожалуйста. У меня есть код без учёта разной ширины столбцов, пыталась сделать это через префиксные суммы, но у меня совсем не получается.

def push(stack, elem):
    stack.append(elem)
    return elem
def top(stack):
    return stack[-1]
def pop(stack):
    return stack.pop()
def size(stack):
    return len(stack)
def power(a, n):
    if n == 0:
        return 1
    elif n % 2 == 0:
        return power(a * a, n // 2)
    else:
        return power(a, n - 1) * a
inf = 2 * power(10, 9) + 1
n = int(input())
wide = []
a = []
for i in range(n):
    ww, aa = map(int, input().split())
    wide.append(ww)
    a.append(aa)
p = [0] * (n + 1)
for i in range(1, n + 1):
    p[i] = p[i - 1] + wide[i -1]    

h = [-inf] + a + [-inf]
ans = [[0, 0] for i in range(n + 2)]
stack = []
push(stack, 0)
for i in range(1, n + 2):
    curr = h[i]
    while h[top(stack)] > curr:
        ans[pop(stack)][1] = i
    push(stack, i)
stack = []
push(stack, 0)
for i in range(n + 1, 0, -1):
    curr = h[i]
    while h[top(stack)] > curr:
        ans[pop(stack)][0] = i
    push(stack, i)
m = -inf
b = 0
for i in range(1, n + 1):
    S = h[i] * (p[i] - p[i] - 1)
    b = 0
    m = max(m, S)
print(m)
1
  • Примите ответ, если он вам помог — галочка около ответа.
    – n1tr0xs
    16 июл 2020 в 20:04

2 ответа 2

2

"Перевел" код Igor на Python:

def maxArea(rs):
    a = 0
    for i in range(len(rs)):
        r = rs[i]
        ai = r[0] * r[1] + back(rs, r[1], i) + forward(rs, r[1], i)
        a = max(a, ai)
    return a

def back(rs, h, idx):
    a = 0
    for j in range(idx-1, -1, -1):
        if rs[j][0] >= h:
            a += rs[j][0] * h
        else:
            break
    return a

def forward(rs, h, idx):
    a = 0
    for j in range(idx+1, len(rs)):
      if rs[j][1] >= h:
        a += rs[j][0] * h
      else:
        break
    return a

rs1 = [[4, 3], [2, 1], [2, 5]]
rs2 = [[4, 3], [2, 1], [3, 5]]

print(maxArea(rs1))
print(maxArea(rs2))
1

function maxArea(rs) {
  var a = 0;
  for (var i = 0; i < rs.length; i++) {
    var r = rs[i];
    var ai = r[0] * r[1] + back(r[1], i) + forward(r[1], i);
    a = Math.max(a, ai);
  }
  return a;
  
  function back(h, idx) {
    var a = 0;
    for (var j = idx - 1; j >= 0; j--) {
      if (rs[j][1] >= h)
        a += rs[j][0] * h;
      else
        break;
    }
    return a;
  }
  function forward(h, idx) {
    var a = 0;
    for (var j = idx + 1; j < rs.length; j++) {
      if (rs[j][1] >= h)
        a += rs[j][0] * h;
      else
        break;
    }
    return a;
  }
}

var rs1 = [[4, 3], [2, 1], [2, 5]];
var rs2 = [[4, 3], [2, 1], [3, 5]];

console.log(maxArea(rs1));
console.log(maxArea(rs2));

2
  • А на каком это языке? Не питон точно... 13 июл 2020 в 2:40
  • @AuroraStepaniuk Да, это JavaScript. Зато запускается прямо здесь. И не в языке же дело.
    – user176262
    13 июл 2020 в 2:50

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.