Идеи для конкретной структуры данных в C++

Question

Мне нужно выполнить некоторые задачи. Есть числа, дающие две строки и они действуют как пары целых чисел (a, b). Я должен найти максимум 5 чисел a-строки, а затем выбрать максимум этих 5, но на этот раз из b-строки. Пример:

1 4 
5 2 
3 3 
7 5 
6 6 
2 9 
3 1 

В этом примере пара я нужен (6,6), так как 6 (а) находится в верхнем 5 а [я] числа и 6 (б) является максимальным в b этих 5 пар. Я думал об этом с помощью векторов и моих собственных определенных структур, также использую некоторые массивы temp, но я не знаю, правильно ли это делать, может быть, есть более простой способ сделать это.

Любые идеи?

EDIT: Мне также нужен номер индекса пары (в случае 5, это пятая пара i.e).

Answer 1

Удовлетворяют пары удержания очереди с приоритетом, которые выполняют оценки порядка, основанные на первом элементе пары. Вы можете вставить все пары, а затем извлечь верхнюю часть 5. Затем просто перейдите в этот список пар, ища максимальный второй элемент каждой пары.

редактировать

я должен сказать, что это достойное решение, только если вы можете принять выполнения порядка О (п * Л.Г. п)

Answer 2

Альтернативные подходы:

Нажмите тройки (первый, второй, индекс) в вектор, а затем std :: partial_sort первые 5 элементов с использованием функтора нисходящего порядка на первом элементе. Затем используйте std :: max_element со вторым функтором, чтобы найти максимум второго элемента и захватите его индекс. Если я правильно читаю сложность partial_sort, это должно выполняться в линейном времени (O (n)), потому что мы всегда сортируем максимум 5 элементов, а не O (n * log n).

Аналогичным образом, чтобы вектор содержал только пары и сортировал второй вектор, содержащий индексы в первом.