Задача про заборы
Помогите Петру и найдите два забора, которые вместе с дорогой образуют максимальный по площади прямоугольный участок, и выведите эту площадь.
Ширина всех участков одинакова и равна 1.
Входные данные (поступают в стандартный поток ввода)
На вход вашей программе подаётся одна строка, содержащая массив целых чисел length, где length[i] - длина i-ого забора. Иными словами i-ый элемент массива задаёт забор в виде отрезка от (i, 0) до (i, length[i]), где 0 - это дорога.
Причём 0 ≤ length[i] ≤ 10 000, а количество заборов n удовлетворяет условию 2 ≤ n ≤ 100 000.
Все входные данные наших тестов всегда соблюдают указанные параметры, дополнительные проверки не требуются.
Выходные данные (ожидаются в стандартном потоке вывода)
Одно целое число, максимальная площадь образованного участка.
Пример 1
Ввод:
2 4 3 2 1 4 1
Вывод:
16
В первом примере участок наибольшей площади образуется между двумя заборами длины 4.
Пример 2
Ввод:
1 2
Вывод:
1
В данном примере второй забор используется не на всю длину, т.к. нас интересуют только прямоугольные участки.
Мой код:
line = input()
length = [int(item) for item in line.split()]
max_area = 0
if length[0] > 0 and length[1] > 0:
max_area = 1
for left in range(0, len(length) - 1):
for right in range(left + 1, min(left + 1 + length[left], len(length))):
min_length = min(length[left], length[right])
width = right - left
if min_length == width:
max_area = max(max_area, min_length * width)
print(max_area)
Тесты пройдены. Но ответ неправильный. Вывод программы не совпал с ожидаемым. Что тут не так?
Ответы (2 шт):
Ваша программа не всегда считает верно. Например, для ввода 100, 100 она вернёт единицу, хотя верный ответ – 100.
Я подозреваю этот кусок: if min_length == width:. Зачем он нужен?
Если условие удалить, пример выше начинает считаться верно. Следующий пример: 2 1 1 2. Ответ программы 2, верный ответ 6.
На этот раз под подозрением min(left + 1 + length[left], len(length)). Зачем нужен первый аргумент min?
Если вместо min подставить его второй аргумент, программа начинает считать верно.
В программе можно ещё кое-что поправить и упростить, но считает она правильно, только медленно. Хотя это тема для отдельного вопроса.
Перебирая каждый элемент массива (кроме последнего), перебираем каждый элемент справа (вложенным циклом) и вычисляем площадь произведением наименьшей длины полученной пары заборов и расстояния между ними (разницы индексов). Наибольший результат возвращаем.
Код на JS.
function findMaxArea(input_arr){
let max_area = 0;
for(let i=0; i < input_arr.length-1; i++){
for(let j=i+1; j < input_arr.length; j++){
max_area = Math.max(max_area, (j-i)*Math.min(input_arr[i], input_arr[j]));
}
}
return max_area;
}
console.log(findMaxArea([1,2]));
console.log(findMaxArea([2,4,3,2,1,4,1]));Более рациональная версия. Идем от обоих концов массива одновременно. Начальная наибольшая площадь: произведение минимального из длин по концам и длины массива - 1. Ищем больший вариант сдвигаясь с концов к середине до сближения левого и правого концов.
Сдвигаемся со стороны наименьшей длины забора (при равенстве сначала вправо, а затем сохраняем направление). Как только находится забор большей длины на направлении - пересчитываем площадь, сохраняем наибольший результат.
function findMaxArea(arr) {
let l = 0;
let r = arr.length - 1;
let max_area = Math.min(arr[l], arr[r]) * (r - l);
let longest_left = arr[l];
let longest_right = arr[r];
let to_right = longest_left <= longest_right;
while (r - l > 1) {
if (to_right) {
l++;
if (arr[l] <= longest_left) {
continue;
} else {
longest_left = arr[l];
if (longest_left > longest_right) {
to_right = false;
}
}
} else {
r--;
if (arr[r] <= longest_right) {
continue;
} else {
longest_right = arr[r];
if (longest_right > longest_left) {
to_right = true;
}
}
}
max_area = Math.max(max_area, Math.min(arr[l], arr[r]) * (r - l));
}
return max_area;
}
console.log(findMaxArea([1, 2]));
console.log(findMaxArea([2, 4, 3, 2, 1, 4, 1]));