Количество пар

Общая идея

В некоторых задачах при разумных ограничениях можно написать квадрат.

В остальных похожие идеи, что и в Количество таких-то подотрезков.

Задача 9794

Условие

Менеджер по работе с персоналом присваивает рейтинговый балл каждому из N кандидатов, резюме которых он изучает. Он хочет нанять двух специалистов с суммарным рейтингом не менее К баллов. Требуется по имеющимся данным о баллах N кандидатов определить, сколько различных пар кандидатов можно выбрать так, чтобы их суммарный рейтинговый балл составлял не менее К. Две пары кандидатов считаются различными, если хотя бы один из членов пары не присутствует в другой паре. Запишите в ответе найденное количество пар.

Разбор

Нужно посчитать количество пар i, j таких что i < j и a[i] + a[j]>= k. Будем перебирать первого кандидата, и также поддерживать второй указатель j, он будет минимальным индексом таким что a[i] + a[j] >= k, либо j = n если такого нет, если мы его знаем, то к ответу нужно просто прибавить n - j, так как если нам подходит a[j], то подходит a[j + 1], a[j + 2] и тд. И так как j > i то берем максимум из i + 1, j + 1.

Код

Похожие задачи:

Задача 69

Условие

На вход программы поступает последовательность из N целых положительных чисел. Рассматриваются все пары различных элементов последовательности. Необходимо определить количество пар чисел, разность которых кратна 13, а произведение чётно.

Разбор

В этой задаче n маленькое поэтому можно написать тупое решение и подождать не более минуты пока найдется ответ. Двумя форами переберем все различные пары чисел и проверим условие данное в задаче. Перебираем пары (i, j) и проверяем что a[i] * a[j] % 2 == 0 и (a[i] - a[j]) % 13 == 0. В конце выводим ответ.

Код

Похожие задачи: