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

Question

[Leevz]

Условия задачи:

Есть определенный вид налога для турфирм, которая организовывают маршруты по горам, его величина зависит только от горизонтального перемещения, и совсем не зависит от высоты гор. На вход программы подаются: сначала число 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. Пояснение: поскольку высоты монотонно убывают, маршрут составить не получится.

Comments

[Saboteur]

Это задание, а не вопрос.
Обратитесь на фриланс - вам решат.

[Leevz]

Saboteur, согласен, однако денег у меня нет на фриланс у меня нет :/

Answer 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;
	}

Comments

[Leevz]

спасибо! Не додумался записывать лучший результат в переменные, записывал минимальные пути в массив

using namespace std;

	int N;
	cin >> N;
	vector<int> apex(N);

	struct route {
		int start{ -1 };
		int end{ -1 };
	};

	vector<route> arrayRoute(static_cast<int>(N / 3) + 1);
	int routeIndex{ 0 };

	for (int i{ 0 }; i < N; ++i)
		cin >> apex[i];

	bool isRouteFound{ false };
	for (int i{ 1 }; i < N - 1; ++i)
	{
		if (apex[i - 1] < apex[i])
		{
			int relIndex = i;
			while (apex[relIndex] == apex[relIndex + 1])
				++relIndex;
			if (apex[relIndex] > apex[relIndex + 1])
			{
				arrayRoute[routeIndex].start = i;
				arrayRoute[routeIndex].end = relIndex + 2;
				++routeIndex;
				isRouteFound = true;
			}
		}
	}

	if (!isRouteFound)
		cout << 0;
	else
	{
		int minRouteIndex{ 0 }, i{ 0 };
		while (arrayRoute[i + 1].start != -1)
		{
			if (arrayRoute[i + 1].end - arrayRoute[i + 1].start < arrayRoute[i].end - arrayRoute[i].start)
				minRouteIndex = i + 1;
			++i;
		}

		cout << '\n' << arrayRoute[minRouteIndex].start << '\n' << arrayRoute[minRouteIndex].end;
	}