@Leevz

Как решить задачу на вершины на C++ с минимальным кодом?

Условия задачи:
Есть определенный вид налога для турфирм, которая организовывают маршруты по горам, его величина зависит только от горизонтального перемещения, и совсем не зависит от высоты гор. На вход программы подаются: сначала число N, которое означает число высот вершин, которые будут введены, далее вводятся сами высоты вершин. Чтобы сэкономить на налоге, требуется составить минимальный маршрут, но поскольку маршрут проходит по горам, то должен быть подъем и спуск, то есть должна быть точка, которая находится строго выше начала и конца маршрута. Программа должна выводить два числа, номер вершин, в которых маршрут был начат и соответственно закончен. Если не получилось составить маршрут удовлетворяющий условию, вывести 0. Пример входных данных: 7 18 10 15 20 20 10 3, соответствующие выходные данные: 3 6. Пояснение, самый короткий маршрут здесь будет 15 20 20 10, 15 находится под номером 3, а 10 под номером 6. Второй пример. Входные данные: 3 9 8 5, выходные данные: 0. Пояснение: поскольку высоты монотонно убывают, маршрут составить не получится.
  • Вопрос задан
  • 191 просмотр
Решения вопроса 1
std::vector<int> heights{18, 10, 15, 20, 20, 10, 3} ;
	size_t bestLen = 0;
	size_t bestIndex = 0;
	// путь не может быть проложен из последних двух вершин
	for(size_t i = 0; i < heights.size() - 2; ++i)
	{
		// начало пути должно быть в гору
		if(heights[i + 1] <= heights[i])continue;

		// прокладываем путь до ближайшего спуска
		for(size_t j = i + 2; j < heights.size(); ++j)
		{
			if(heights[j] > heights[j-1])break; // подъём встретился до спуска, решение заведомо неоптимально
			if(heights[j] < heights[j-1])
			{
				size_t len = j - i;
				if(len < bestLen || bestLen == 0)
				{
					bestLen = len;
					bestIndex = i;
				}
				break;
			}
		}
	}

	if(bestLen == 0)
	{
		std::cout << 0 << std::endl;
	}
	else
	{
		std::cout << bestIndex + 1 << " " << bestIndex + bestLen + 1 << std::endl;
	}
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

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

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