Идеи для конкретной структуры данных в 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 (a) находится в верхних 5 из чисел a [i], а 6 (b) - максимум в секции b этих 5 пар , Я думал о том, чтобы делать это с векторами и моими собственными определенными структурами, а также использовать некоторые временные массивы, но я не знаю, правильно ли это делать, возможно, есть более простой способ сделать это.

Есть идеи?

РЕДАКТИРОВАТЬ: мне также нужен индексный номер пары (в случае, если это 5, это пятая пара, т.е.).

Answer 1

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

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

Я должен сказать, что это достойное решение, только если вы можете принять время выполнения порядка O (n * lg n)

Answer 2

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

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

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