Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.80/5: Рейтинг темы: голосов - 5, средняя оценка - 4.80
0 / 0 / 0
Регистрация: 02.09.2019
Сообщений: 4
1

проблема с задачей на поиск оптимального маршрута

02.09.2019, 19:34. Показов 966. Ответов 6
Метки нет (Все метки)

Бандит хочет ограбить n банков, все банки расположены на прямой. Позиция банка с номером
i характеризуется целым числом a(i) — координатой этого банка (в км) на прямой. Перед началом
операции бандит может подъехать сразу к любому банку. Выяснилось, что из банка index деньги увезут в неизвестном направлении ровно через t минут после начала! При этом банк можно успеть ограбить в момент t, но не
позже.
Если бандит не ограбит хотя бы один банк, операция провалилась. Бандит ездит со скоростью не выше 60 км/ч (1 км в минуту).
Составьте самый оптимальный маршрут, следуя которому, он успеет ограбить все банки. Если таких маршрутов несколько, устроит любой. Можете считать, что благодаря отточенному мастерству бандит грабит любой банк моментально.

Формат входных данных
В первой строке заданы числа n и t
Во второй строке задано n чисел a(i)
В третьей строке задано число index

Формат выходных данных
В первой строке выведите число минут, которое потребуется бандиту для ограбления всех банков.
Во второй строке выведите n чисел — порядок ограбления банков.

Примеры
Ввод:
5 5
1 4 9 16 25
2
Вывод:
24
1 2 3 4 5
Ввод:
6 4
1 2 3 6 8 25
5
Вывод:
31
5 4 3 2 1 6


Вот мой код

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <iostream>
 
void print(int i, int j) 
{
    if (i <= j) 
    {
        for (; i <= j; i++) 
        {
            std::cout << i << ' ';
        }
    }
    else {
        for (; i >= j; i--) 
        {
            std::cout << i << ' ';
        }
    }
}
 
int main()
{
    int n, t, ind;
    int arr[100];
    std::cin >> n >> t;
    for (int i = 0; i < n; ++i) 
    {
        std::cin >> arr[i];
    }
    std::cin >> ind;
 
    int lhs = arr[ind - 1] - arr[0];
    int rhs = arr[n - 1] - arr[ind - 1];
    if (lhs <= t) 
    {
        std::cout << arr[n - 1] - arr[0] << '\n';
        print(1, n);
    }
    else if (rhs <= t) 
    {
        std::cout << arr[n - 1] - arr[0] << '\n';
        print(n, 1);
    }
        else 
        {
            if (lhs <= rhs) 
            {
                std::cout << lhs * 2 + rhs << '\n';
                print(ind, 1);
                print(ind + 1, n);
            }
            else 
            {
                std::cout << lhs + rhs * 2 << '\n';
                print(n, n + 2 - ind);
                print(1, n + 1 - ind);
            }
        }
 
    return 0;
}
Не проходит почти последний тест WA. Где я допустил ошибку?
0

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
02.09.2019, 19:34
Ответы с готовыми решениями:

Поиск оптимального маршрута
Не нашел на форуме подходящей темы и решил создать свою...если уже было--поделитесь ссылочкой ...

Задача на поиск оптимального маршрута
Привет, возникла проблема с программой на прологе, вот задание: Выбор оптимального маршрута...

Навигатор (поиск оптимального маршрута)
Помогите задали курсач РАзработки программы для поиска оптимального маршрута (задана карта...

Предлагаю задачку - поиск оптимального маршрута
Один из моих заказчиков занимается логистикой и транспортной экспедицией, я время от времени вношу...

6
170 / 122 / 61
Регистрация: 06.02.2015
Сообщений: 300
02.09.2019, 19:44 2
Повтор
Массив: Последнее дело Оушена. Составьте маршрут, следуя которому, Оушен успеет ограбить все банки.

C++
1
int lhs = arr[ind - 1] - arr[0];
если ind=0 , будет нехорошо
0
0 / 0 / 0
Регистрация: 02.09.2019
Сообщений: 4
02.09.2019, 20:21  [ТС] 3
ind может быть 0 только если 2 банка находятся в одном месте, но такое невозможно
0
811 / 499 / 210
Регистрация: 19.01.2019
Сообщений: 1,196
02.09.2019, 20:26 4
Цитата Сообщение от yanOlerinskiy Посмотреть сообщение
Вот мой код
Это мой код. И я понятия не имею, почему он валится
0
0 / 0 / 0
Регистрация: 02.09.2019
Сообщений: 4
02.09.2019, 20:28  [ТС] 5
ну вот человек написал, что 0 возможен, не знаете откуда эта задача? вроде обычная на информатиксе, а так много просмотров
0
811 / 499 / 210
Регистрация: 19.01.2019
Сообщений: 1,196
02.09.2019, 20:31 6
Вам скинули ссылку, там я её и нашёл. Там хоть условия нормально прописаны. Где
В первой строке заданы числа n и t (1 <= n, t <= 100).
Во второй строке задано n чисел ai (|ai| <= 100), расположенных в порядке возрастания.
В третьей строке задано число index (1 <= index <= n).
?
0
0 / 0 / 0
Регистрация: 02.09.2019
Сообщений: 4
02.09.2019, 20:31  [ТС] 7
тут можно удалять тему?
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
02.09.2019, 20:31

Помощь в написании контрольных, курсовых и дипломных работ здесь.

выбор оптимального маршрута
Всем доброго времени суток. В качестве дипломного проекта я занимаюсь маршрутизацией БПЛА....

Расчет оптимального маршрута
Хелпаните) Надо написать программу в среде разработки Visual C#, определяющую оптимальный маршрут...

Функция определения более оптимального маршрута по времени
Надо написать для структуры функцию определения более оптимального маршрута по времени. Написал, но...

Определить длину самого оптимального маршрута движения человека
Даны координаты четырех точек на плоскости (x1, y1, x2, y2, x3, y3, x4, y4). Человек может начинать...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
7
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.