MiddleКодИногдаЕщё не отвечали
Подсчёт пар индексов с разностью значений не меньше K
Дан массив целых и K >= 0. Посчитайте пары индексов (i, j) с i <= j, у которых разность значений |a[i] - a[j]| не меньше K. При K = 0 считается каждая пара, включая самопару (i, i).
Требования:
- Лучше, чем O(n²): сортировка, затем подсчёт двумя указателями или бинпоиском.
long long countPairsWithDiff(std::vector<int> a, int K) {
// ваш код здесь
}Допишите реализацию.
Отсортируйте массив. Для каждого i бинпоиском найдите первый индекс со значением не меньше a[i]+K; каждый элемент оттуда до конца образует валидную пару, прибавьте их число. При K = 0 так считаются все пары i <= j. Итого O(n log n) — намного лучше цикла за O(n²).
- ✗Забыть, что при K=0 в подсчёт входит самопара (i, i)
- ✗Считать упорядоченные пары, когда спецификация просит i <= j (или наоборот)
- ✗Использовать исходные индексы и не заметить, что сортировка допустима, ведь важны лишь значения
- →Как изменился бы подход для пар с разностью не больше K (вместо не меньше)?
- →Почему сортировка безопасна, хотя в вопросе упомянуты индексы?
Оглавление
Задача
Посчитайте пары (i, j), i <= j, с разностью значений не меньше K, лучше чем за O(n²).
Решение
#include <vector>
#include <algorithm>
long long countPairsWithDiff(std::vector<int> a, int K) {
std::sort(a.begin(), a.end());
long long total = 0;
int n = a.size();
for (int i = 0; i < n; ++i) {
// первый j со значением >= a[i] + K
long long target = static_cast<long long>(a[i]) + K;
int j = std::lower_bound(a.begin() + i, a.end(), target) - a.begin();
total += n - j; // все справа от j подходят
}
return total;
}Ключевые моменты
- Сортировка даёт O(n log n): каждый
iсчитает партнёров бинпоиском. - При
K = 0lower_boundуказывает на самa[i], учитывая парыi <= j. - Считаем только пары
i <= j, а не упорядоченные.
Оглавление
