nicknamecsharp
@nicknamecsharp

Как решить задачу линейным алгоритмом?

Задачу решить могу, но вообще не выкупаю, почему в первом тесте ответ 2 5, а не 1 4:

Отношение
Дан массив a1,a2,...an. Необходимо выбрать в нём два элемента ai и aj, такие что i < j,
и отношение aj/ai — максимально и больше 1.

Входные данные

В первой строке задано целое число 2 ⩽n⩽ 100 000 — количество элементов в массиве.

Во второй строке заданы n целых положительных чисел ai(1 ⩽i⩽n, 1 ⩽ai⩽ 5000).

Выходные данные

Выведите два числа — индексы элементов i и j. Если ответов несколько, то выведите любой из них.

Если ответа нет, то выведите два нуля, разделённых пробелом.

Тесты

6
10 3 5 3 11 9
2 5

4
5 5 5 5
0 0
  • Вопрос задан
  • 772 просмотра
Решения вопроса 1
Alexandroppolus
@Alexandroppolus
кодир
Это задача про однократную покупку/продажу акции. Решается за один проход, просто надо помнить текущий максимум aj/ai, и минимальное ai (чтобы на него делить очередное значение), и соответственно индексы, при которых эти рекорды были достигнуты.

почему в первом тесте ответ 2 5, а не 1 4
индексы здесь начинаются с 1, а не с 0.
Паскальщик составлял.
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
Rsa97
@Rsa97
Для правильного вопроса надо знать половину ответа
1 ⩽ i ⩽ n
Ответ написан
Комментировать
Ваш ответ на вопрос

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

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