@Nikitos2002

K-ая порядковая статистика. В чем проблема?

Добрый вечер. Написал программу для поиска К-ой порядковой статистики, в качестве основы взял алгоритм быстрой сортировки. Программа дает неправильный ответ на 8 тесте. В чем может быть проблема?
Задача
Дан массив из n элементов. Какое число k-ое в порядке возрастания в этом массиве?

Формат входного файла
В первой строке входного файла содержатся два числа n размер массива и
k.(1 <= k <= n <= 3 * 10^7). Во второй строке находятся числа A, B, C, a1, a2 по модулю не
превосходящие 10^9. Вы должны получить элементы массива начиная с третьего по формуле:
a[i] = A * a[i-2] + B * a[i-1] + C. Все вычисления должны производится в 32 битном знаковом типе,
переполнения должны игнорироваться.

Формат выходного файла
Выведите k-ое в порядке возрастания число в массиве a.

Мой код:
#include <iostream>
#include <fstream>

int partition(int l, int h, int* array)
{
	int i = l, j = h;
	int pivot = array[l];
	while (i < j)
	{
		do {
			i++;
		} while (array[i] <= pivot);
		do {
			j--;
		} while (array[j] > pivot);                       
		if (i < j)
			std::swap(array[i], array[j]);
	}
	std::swap(array[j], array[l]);
	return j;
}

int quick_sort(int l, int h, int* array, int k)
{
	int pivot_index;
	if (l < h)
	{

		pivot_index = partition(l, h, array);
		if (k < pivot_index)
			quick_sort(l, pivot_index, array, k);
		else
			quick_sort(pivot_index + 1, h, array, k);
	}
	return array[k];
}


int main()
{
	std::ifstream fin;
	fin.open("kth.in");
	std::ofstream fout;
	fout.open("kth.out");

	int size, k;
	fin >> size >> k;
	int A, B, C;
	fin >> A >> B >> C;
	int* array = new int[size];
	fin >> array[0] >> array[1];
	for (int i = 2; i < size; i++)
	{
		array[i] = A * array[i - 2] + B * array[i - 1] + C;
	}

	fout << quick_sort(0, size, array, k-1);

	fin.close();
	fout.close();
	return 0;
}
  • Вопрос задан
  • 1430 просмотров
Решения вопроса 1
wataru
@wataru Куратор тега C++
Разработчик на С++, экс-олимпиадник.
У вас какая-то странная схема в partition.

Представьте, что у вас массив из 2 элементов и первый - больше второго (a[0] = pivot > a[1]).

До цикла l = 0, h = 2, i = 0. Потом в первом while вы делаете i++. Потом сравниваете a[i] с pivot в первом while. a[1] < pivot по предположению, поэтому вы делаете i = 2. Все - вы уже вышли за границу массива.

Перепишите со стандартной схемой разбиения Хоара или Ломуто.

Или придется всякие условия i < j везде дописывать, но я не уверен.
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

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

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