@Nikitos2002

Как посчитать количество инверсий, используя сортировку слиянием?

Добрый вечер. Решил задачу и с полной уверенностью загрузил ее в проверяющую систему. В итоге неправильный ответ на 7 тесте.
Не могли бы, пожалуйста, помочь?
Мой код:
#include <iostream>
#include <fstream>
int* input_array(int* len)
{
	std::ifstream fin;
	fin.open("inversions.in");
	fin >> *len;
	int* array = new int[*len];
	for (int i = 0; i < *len; i++)
		fin >> array[i];
	fin.close();
	return array;
}

void Merge_Sort(int* array, int array_size, int* number_of_inversitions)
{
	if (array_size <= 1) return;

	int middle = array_size / 2;
	int left_size = middle;
	int right_size = array_size - middle;
	int* left = array;
	int* right = array + left_size;

	Merge_Sort(left, left_size, number_of_inversitions);
	Merge_Sort(right, right_size, number_of_inversitions);

	int left_index = 0;
	int right_index = 0;
	int index = 0; 
	int* temp_array = new int[array_size];
	while (left_index < left_size and right_index < right_size)
	{
		if (left[left_index] <= right[right_index])
			temp_array[index++] = left[left_index++];
		else {
			temp_array[index++] = right[right_index++];
			*number_of_inversitions += left_size - left_index;
		}
	}

	while (left_index < left_size)
		temp_array[index++] = left[left_index++];
	while (right_index < right_size)
		temp_array[index++] = right[right_index++];

	for (int i = 0; i < array_size; i++)
		array[i] = temp_array[i];
	delete[] temp_array;
}

int main()
{
	std::ofstream fout;
	fout.open("inversions.out");
	int number_of_inversitions = 0, n;
	int* array;
	array = input_array(&n);
	Merge_Sort(array, n, &number_of_inversitions);
	fout << number_of_inversitions;
	delete[] array;
	fout.close();
	return 0;
}
  • Вопрос задан
  • 37 просмотров
Решения вопроса 1
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, гуглер, экс-олимпиадник.
Вроде все правильно. Какие ограничения? Может быть переполнение, ведь максимальный ответ n(n-1)/2. Для переполнения int достаточно 65536 чисел в массиве.
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

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

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