|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
09.03.2019, 00:15 | #1 |
Новичок
Джуниор
Регистрация: 08.03.2019
Сообщений: 2
|
Прыжки по зданиям (C++)
В городе есть n зданий с высотами h1; h2; ...; hn. Мальчик любит прыгать по зданиям и может прыгнуть из одного здания на другое только тогда, когда их высоты одинаковы и высоты всех зданий между ними не превышает высоты текущего здания.
Вам нужно посчитать количество таких пар зданий, которые мальчик может перепрыгнуть с одного дома на другой. Входные данные: В первой строке записано целое число n (n ≤ 3 * 10^5). Во второй строке записаны n целых чисел h1; h2 ...; hn (1 ≤ hi ≤ 10^6). Входные данные: Выведите единственное целое число - ответ на задачу. Пример 1: Ввод 6 3 2 1 2 3 3 Вывод 8 Пример 2: Ввод 3 1 1000 1 Вывод 0 В примере 1 каждая из следующих пар считается в ответе два раза (в прямом и перевернутом порядке): (1, 5); (1, 6); (5, 6); (2, 4). Задание нужно решить с использованием дерева отрезков, иначе не пройдет по времени. Начал чтото делать: Код:
Вот мой вариант решения перебором: Код:
Можете подправить код? Проверте следующие тесты: Тест #1. 2 6 6 Можно перепрыгнуть: (1, 2); Ответ 2. (Но выводится 0). Тест #2. 6 5 4 3 3 4 5 Можно перепрыгнуть: (1, 6); (2, 5); (3, 4). Ответ 6. (Но выводится 4). Тест #3. 6 3 4 5 5 4 3 Можно перепрыгнуть: (3, 4); Ответ 2. (Но выводится 4). Гляньте пожалуйста. |
09.03.2019, 00:21 | #2 |
Новичок
Джуниор
Регистрация: 08.03.2019
Сообщений: 2
|
Думаю, для каждого здания деревом отрезков найти следующее по высоте справа. А потом посчитать сколько таких же зданий на этом отрезке. Но как это сделать програмно? Какие части псевдокодов дерева отрезков нужно использавать?
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
когда написал код про прыжки,хочу открыть игру,но просто чёрный экран,а вот когда нажимаю на "Крестик" вижу этот квадратик который в игре на секунду,и всё | SashaBiven | Python | 1 | 05.12.2018 08:30 |
Создание приложения (по карте города и некоторым зданиям в городе) | Snow811 | Помощь студентам | 1 | 03.04.2014 10:28 |