@Crypton88

Доработка алгоритмической задачи JAVA. Требуется помощь >?

Ниже приведу задачу.

После очередного завершённого проекта программист Пётр решил переехать в деревню и заняться сельским хозяйством. Мелочиться он не стал, поэтому помимо домика в деревне сразу приобрёл несколько идущих подряд параллельных участков поля, расположенных вдоль прямой дороги. Участки были разделены заборами, при этом все заборы начинались от той самой дороги, но заканчивались на разном удалении от неё не доходя до противоположной границы участка.
Петру нужно объединить эти участки. Но так как Пётр перфекционист, он непременно хочет, чтобы получившийся объединённый участок:
1. был прямоугольным;
2. был ограничен дорогой и двумя уже имеющимися заборами (забор необязательно использовать целиком, а вот удлинять забор нельзя);
3. имел наибольшую возможную площадь.
Как и положено разработчику Пётр получает 300к/наносек, поэтому его совсем не беспокоит тот факт, что часть территории окажется неиспользованной.
Пётр хочет отдохнуть, поэтому он попросил вас помочь с нахождением площади такого участка.
Помогите Петру и найдите два забора, которые вместе с дорогой образуют максимальный по площади прямоугольный участок, и выведите эту площадь.
Ширина всех участков одинакова и равна 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
В данном примере второй забор используется не на всю длину, т.к. нас интересуют только прямоугольные участки.

Мой код выглядит так:
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String build = scanner.nextLine();
        String[] list = build.split(" ");
        int[] line = new int[list.length];
        for (int i = 0; i < list.length; i++) {
            line[i] = Integer.parseInt(list[i]);
        }
        int firtst = 0, second = 0, firtIndex = 0, secondIndex = 0;
        for (int i = 0; i < line.length; i++) {
            if (line[i] > firtst) {
                second = firtst;
                secondIndex = firtIndex;
                firtst = line[i];
                firtIndex = i;
            } else if (line[i] > second) {
                second = line[i];
                secondIndex = i;
            }
        }
        int result = (Integer.max(secondIndex,firtIndex) - Integer.min(secondIndex,firtIndex)) * Integer.min(firtst,second);
        System.out.println(result);
    }
}

удовлетворяет примеру, но решение конкретное не принимает, пишет - ответ не верный. Проблема состоит в том, что он ищет 2 максимума и считает площадь, но по условию нужно найти МАКСИМАЛЬНУЮ площадь. т.е на примере 4 5 4 алгоритм завалится и выдаст ответ - 4, хотя по факту - правильный ответ 8((2-0) * 4). как его доработать ?
  • Вопрос задан
  • 1135 просмотров
Пригласить эксперта
Ответы на вопрос 2
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Вы не ищите 2 максимума, а перебирайте все пары заборов, считайте площадь и выбирайте лучший вариант. Это точно будет работать, хоть и за квадрат.

Есть более хитрое решение за линию. Вот два самых крайних забора, они могут быть вариантом ответа. В противном случае можно выкинуть из рассмотрения кротчайший из них: если он и есть в максимальном ответе, то можно сдвинуть вторую границу на другой крайний отрезок и ответ не ухудшится.

Поэтому решение будет из двух указателей - левого и правого. Пока они не сошлись, считайте площадь, сравнивайте ее с текущим ответом, а потом двигайте указатель на меньшее число в сторону второго.
Ответ написан
@Merphi
Решал такую же задачу, но у меня все просто и без указателей.
есть наборы данных для тестирования? потому как предложенные наборы считает верно, Ваш вариант 4 5 4 тоже нормально считает, но все равно при проверке в Школе выдает неправильный ответ
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы